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:  };