【LeetCode】259 3Sum Smaller

题目：

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[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^2) runtime?

题解：

　　(我没舍得花钱。。。咳咳，这样不太好QAQ，代码都没有提交过，所以以后来看得注意一下代码的正确性。)

　　老规矩，第一个想法是啥？必须的暴力解啊，哈哈，虽然时间复杂度是O(n^3);这里

Solution 1 ()

 class Solution {

 public:

     int threeSumSmaller(vector<int>& nums, int target) {

         int cnt = ;

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

         int n = nums.size();

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

             if(i> && nums[i] == nums[i-]) continue;

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

                 if(j>i+ && nums[j] == nums[j-]) continue;

                 for(int k=j+; k<n; k++) {

                     if(k>j+ && nums[k] == nums[k-]) continue;

                     if(nums[i] + nums[j] + nums[k] < target) cnt++;

 　　　　　　　　　　　　else break;

                 }

             }

         }

     }

 };

　　若想时间复杂度为O(n^2)，那么就需要和之前的3Sum题目一样，两指针为剩余数组的头尾指针，搜索遍历。这里需要注意的是，当sum<target时，cnt需要加上k-j，而不是cnt++，因为数组已经排好序，若尾指针当处于位置k时满足条件，则j<position<=k的pos都满足这个条件，故cnt需加上k-j.

Solution 2 ()

 class Solution {

 public:

     int threeSumSmaller(vector<int>& nums, int target) {

         int cnt = ;

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

         int n = nums.size();

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

             if(i> && nums[i] == nums[i-]) continue;

             int j = i + , k = n - ;

             while(j<k) {

                 int sum = nums[i] + nums[j] + nums[k];

                 if(sum < target) {

                     cnt += k - j;

                     j++;

                 }

                 else k--;

             }

         }

         return cnt;

     }

 };

巴特西

【LeetCode】259 3Sum Smaller

最新文章

热门文章