018_四数之和

2019-03-10 11:48:16来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

 1 //使用三数之和中的双指针的思想,固定外围两个数
 2 vector<vector<int>> fourSum(vector<int>& nums, int target) {
 3     sort(nums.begin(), nums.end());
 4     vector<vector<int>>Res;
 5     if (nums.size() < 4)return Res;
 6     for (int d = nums.size() - 1; d >= 3;) {
 7         for (int a = 0; a < d;) {
 8             for (int b = a + 1, c = d - 1; b < c;) {
 9                 if ((nums[a] + nums[b] + nums[c] + nums[d]) < target)//小了,要大点
10                     ++b;
11                 else if ((nums[a] + nums[b] + nums[c] + nums[d]) > target)//太大了,要小点
12                     --c;
13                 else {//刚好为0
14                     vector<int>v = { nums[a],nums[b] ,nums[c], nums[d] };
15                     Res.push_back(v);
16 
17                     do
18                     {
19                         ++b;
20                     } while (b < c && nums[b] == nums[b - 1]);//去除重复数字
21 
22                     do
23                     {
24                         --c;
25                     } while (c > b && nums[c] == nums[c + 1]);//去除重复数字
26 
27                 }
28             }
29             do
30             {
31                 ++a;
32             } while (a < d && nums[a] == nums[a - 1]);//去除重复数字
33         }
34 
35         do
36         {
37             --d;
38         } while (d >= 3 && nums[d] == nums[d + 1]);//去除重复数字
39     }
40 
41     return Res;
42 
43 }

 


原文链接:https://www.cnblogs.com/zzw1024/p/10489826.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++_调用约束

下一篇:c/c++面试指导---c语法总结