121. Best Time to Buy and Sell Stock

This is actually a maximum subarray sum problem which can be solved by Kadane’s Algorithm.
Here is a very good video explaining this algorithm:
https://www.youtube.com/watch?v=86CQq3pKSUw

1:  class Solution {  
2:  public:  
3:    int maxProfit(vector<int>& prices) {  
4:      int maxGlobal = 0;  
5:      int maxCurrent = 0;  
6:      for (int i = 1; i < prices.size(); i++) {  
7:        maxCurrent = max(prices[i]-prices[i-1], maxCurrent + prices[i]-prices[i-1]);  
8:        if (maxCurrent > maxGlobal) maxGlobal = maxCurrent;  
9:      }  
10:      return maxGlobal;  
11:    }  
12:  };  

259. 3Sum Smaller

For a sorted array, if we fixed a number nums[i], and search from two ends of the rest array, i.e. nums[left], nums[right] where left and right is initialized by i+1 and nums.size()-1 respectively, we’ll see that if nums[left] + nums[right] >= target - nums[i], we want to move the right end to left. Once nums[left] + nums[right] < target - nums[i], we know that all numbers in [left, right] will there will be (right - left) triples that satisfy their sum less than target.

1:  class Solution {  
2:  public:  
3:    int threeSumSmaller(vector<int>& nums, int target) {  
4:      if (nums.size() < 3) return 0;  
5:      int count = 0, left = 0, right = nums.size()-1;  
6:      sort(nums.begin(), nums.end());  
7:      for (int i = 0; i < right && i < nums.size()-2; i++) {  
8:        if (nums[i] + nums[i+1] + nums[i+2] >= target) break;  
9:        int left = i+1, right = nums.size()-1;  
10:        int t = target - nums[i];  
11:        while (left < right) {  
12:          while (left < right && nums[left] + nums[right] >= t) right--;  
13:          count += right - left;  
14:          left++;  
15:        }  
16:      }  
17:      return count;  
18:    }  
19:  };  

When I revisited this problem, I found a more concise way though the idea behind is still the same.

1:  class Solution {  
2:  public:  
3:    int threeSumSmaller(vector<int>& nums, int target) {  
4:      if (nums.size() < 3) return 0;  
5:      sort(nums.begin(), nums.end());  
6:      int count = 0;  
7:      for (int i = 0; i < nums.size()-2; i++) {  
8:        int j = i+1, k = nums.size()-1, t = target - nums[i];  
9:        while (j < k) {  
10:          if (nums[j] + nums[k] >= t) k--;  
11:          else count += k - j++;  
12:        }  
13:      }  
14:      return count;  
15:    }  
16:  };  

4Sum

My intuition is derive the solution from 3Sum. Basically, the same idea.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> fourSum(vector<int>& nums, int target) {  
4:      vector<vector<int>> res;  
5:      bool flag = false;  
6:      if (nums.empty()) return res;  
7:      sort(nums.begin(), nums.end());  
8:      for (int i = 0; i < (int)nums.size()-3; i++) {  
9:        if (i > 0 && nums[i] == nums[i-1]) continue;  
10:        int sum3 = target-nums[i];  
11:        flag = false;  
12:        for (int j = i+1; j < (int)nums.size()-2; j++) {  
13:          if (flag && nums[j] == nums[j-1]) continue;  
14:          flag = true;  
15:          int sum2 = sum3-nums[j];  
16:          int start = j+1, end = nums.size()-1;  
17:          while (start < end) {  
18:            if (nums[start]+nums[end]==sum2) {  
19:              vector<int> sol;  
20:              sol.push_back(nums[i]);  
21:              sol.push_back(nums[j]);  
22:              sol.push_back(nums[start++]);  
23:              sol.push_back(nums[end--]);  
24:              res.push_back(sol);  
25:              while (start < end && nums[start] == nums[start-1]) start++;  
26:              while (start < end && nums[end] == nums[end+1]) end--;  
27:            } else if (nums[start]+nums[end]<sum2) {  
28:              start++;  
29:            } else {  
30:              end--;  
31:            }  
32:          }  
33:        }  
34:      }  
35:      return res;  
36:    }  
37:  };  

15. 3Sum

The idea is to sort the array first and scan the array from left to right. When scanning the array, we fix the current element and start check its right subarray by two pointers. Since the array is sorted, for the two pointers, we know that:
1. Sum of nums[i], nums[l], nums[r] is less than target, move the left pointer.
2. Sum of nums[i], nums[l], nums[r] is larger than target, move the right pointer.
3. Target is found, save the triple elements.

Since the problem requires the result to exclude dups, I first tried to use set to store the triples but got TLE. Then I have to add line 8, 13-14 to achieve the requirement.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> threeSum(vector<int>& nums) {  
4:      vector<vector<int>> res;  
5:      if (nums.size() < 3) return res;  
6:      sort(nums.begin(), nums.end());  
7:      for (int i = 0; i < nums.size()-2; i++) {  
8:        if (i == 0 || nums[i-1] != nums[i]) {  
9:          int l = i+1, r = nums.size()-1, t = -nums[i];  
10:          while (l < r) {  
11:            if (nums[l]+nums[r]==t) {  
12:              res.push_back(vector<int>{nums[i],nums[l],nums[r]});   
13:              while ((l < r) && (nums[l] == nums[l+1])) l++;  
14:              while ((l < r) && (nums[r] == nums[r-1])) r--;  
15:              l++, r--;  
16:            }  
17:            else if (nums[l]+nums[r]<t) l++;  
18:            else r--;  
19:          }  
20:        }  
21:      }  
22:      return res;  
23:    }  
24:  };