LeetCode 题解(270) : 3Sum Smaller

本文主要是介绍LeetCode 题解(270) : 3Sum Smaller，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Given an array of n integers nums and a target, find the number of index tripletsi, j, k with 0 <= i < j < k < n that satisfy the conditionnums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n²) runtime?

题解：

一步一步由O(n3)到O(n2)。

class Solution {
public:int threeSumSmaller(vector<int>& nums, int target) {sort(nums.begin(), nums.end());int k = nums.size() - 2;int count = 0;for(int i = 0; i < k; i++) {for(int j = i + 1; j < k + 1; j++) {for(int t = j + 1; t < k + 2; t++) {if(nums[i] + nums[j] + nums[t] < target) {count++;} else {break;}}}}return count;}
};

class Solution {
public:int threeSumSmaller(vector<int>& nums, int target) {sort(nums.begin(), nums.end());int k = nums.size() - 2;int count = 0;for(int i = 0; i < k; i++) {for(int j = i + 1; j < k + 1; j++) {int end = nums.size() - 1;int t = target - nums[i] - nums[j];while(end > j && nums[end] >= t)end--;count += ((end > j) ? (end - j) : 0);}}return count;}
};

class Solution {
public:int threeSumSmaller(vector<int>& nums, int target) {sort(nums.begin(), nums.end());int k = nums.size() - 2;int count = 0;for(int i = 0; i < k; i++) {int begin = i + 1;int end = k + 1;int t = target - nums[i];while(begin < end) {if(nums[begin] + nums[end] >= t) {end--;} else {count += end - begin;begin++;}}}return count;}
};

这篇关于LeetCode 题解(270) : 3Sum Smaller的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---