Container with most water (C++ code)

LeetCode Container With Most WaterJan 9 '12
 难度3，出现频率2
Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

 int maxArea(vector<int> &height) {
     int start = 0, end = height.size() - 1;
     int maxvol = 0;
     while(start < end){
          int temp;
          if(height[start] > height[end]) {
              temp =end--;
          } 
          else temp = start++;
          maxvol = max(maxvol, height[temp] *(end - start + 1));
     }
     
    return maxvol;  
    }

3sum (C++ code)

LeetCode 3Sum Jan 18 '12
难度3，出现频率5

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2) 

思路： 固定第一个元素，另外两个元素由sliding window决定。如何去掉重复元素？

1，第一层循环跳过重复的；

2，第二层循环从两头跳过循环的；

时间复杂度O(n^2) 

 
 vector< vector<int> > threeSum(vector<int> &num){
  
  int n = num.size(); 
  vector< vector<int> > res;
  vector<int> cur;
  
  sort(num.begin(), num.end());

  for(int i = 0; i < n-2; i++){
      if(i > 0 && num[i] == num[i-1]) continue;
      cur.push_back(num[i]);
      int start = i + 1, end = n - 1; 
      while(start < end){
                  if(start > i+1 && num[start] == num[start-1]) {
                           start++; continue;
                           }
                  if(end < n-1 && num[end] == num[end+1]){
                           end--; continue;
                         }
                  int sum = num[i] + num[start] + num[end];
                  if(sum == 0) {
                         cur.push_back(num[start]);
                         cur.push_back(num[end]);
                         res.push_back(cur);
                         cur.resize(1);                        
                         start++;
                         end--;
                         }
                  else if(sum > 0) end--;
                  else start++;
                  }  
      cur.pop_back();
  }
  
 return res;

}

3Sum Closest (C++ code)

 LeetCode: 3Sum Closest II
难度3，出现频率1
Given an array S of n integers, find three integers in S such that the sum closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路: 先排序，然后sliding window，记得每次更新最小和。 时间复杂度O(n^2), 空间O(1)。

int threeSumClosest(vector<int> &num, int target) { 

  int n = num.size(); 

  sort(num.begin(), num.end());

  int sum  = num[0] + num[1] + num[n-1] - target;

  for(int i = 0; i < n -2; i++){

      int start = i + 1, end = n - 1; 
      while(start < end){
                  int temp = num[i] + num[start] + num[end] - target;
                  if(abs(temp) < abs(sum)) sum = temp;
                  if(sum == 0) return target;
                  else if(temp > 0) end--;
                  else start++;
                  }  
  }
 return sum + target; 

} 

3Sum Closest III

Given an array S of n integers, find three integers in S that are closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum is 2. (-1 + 2 + 1 = 2).

求与给定点t距离最近的三个点的和--把点列表每个值x换成|x-t|，则原题转化为求最小的三个值的和---

只需要建三个元素的heap。但求和的时候需要的是x而非|x-t|，两个选择：

1，另建一个flag列表标明每个元素的正负--O(n) space, not good.

2,保持原列表，以|x-t|为条件进行比较。

思路2的c++ code: 

时间复杂度： O(n), 空间复杂度： O(1)

int threeSumClosest(vector<int> &num, int target){
   int sum = 0;
   int maxdist = INT_MAX, maxpt = 0;
 
   for(int i = 0; i < num.size(); i++){
     if(i < 3) {
       sum += num[i];
      }
     if(abs(num[i] - target) < maxdist){
        if(i >= 3){sum = sum + num[i] - num[maxpt];}
        maxdist = abs(num[i] - target);
        maxpt = i;
     }
   }
   return sum;
}