首页 > 代码库 > leet_3Sum

leet_3Sum

2024-09-12 05:37:58   222人阅读

一.问题

技术分享

二.解决方法 

1.这个题类似于在一个给定的数组中找出所有满足给定数值的整数对，先看一下这个问题

这个问题的简单的解题思路就是移动两个指针，便利数组，具体代码：

 1 for(int i=0,j=num.length-1;i<j;)
 2           {
 3             //Move the j-pointer to the left till the sum <=c
 4             if(num[i]+num[j]>0)
 5             {
 6               j--;
 7               continue;
 8             }
 9             if(num[i]+num[j]<0)
10             {
11               i++;
12               continue;
13             }
14             if(num[i]+num[j]==0)
15                 System.out.println(num[i]+" "+num[j]);
16                 i++;
17           }

这样会输出重复的答案

技术分享

2.过滤掉重复的结果

 1 for(int i=0,j=num.length-1;i<j;)
 2           {
 3             //Move the j-pointer to the left till the sum <=c
 4             if(num[i]+num[j]>0)
 5             {
 6               j--;
 7               continue;
 8             }
 9             if(num[i]+num[j]<0)
10             {
11               i++;
12               continue;
13             }
14             if(num[i]+num[j]==0)
15                 System.out.println(num[i]+" "+num[j]);
16                 while(num[i] == num[i+1]) i++;
17                 i++;
18           }

技术分享

3.这道题和sum2问题的本质一样，我们可以设置两层循环，外层循环固定一个给定的target，来找另外两个满足sum是-target的数组

 1 //排序
 2           Arrays.sort(num);
 3           for(int i=0;i<num.length;i++)
 4           {
 5             //不能重复（外层）
 6             if((i>0)&&(num[i]==num[i-1]))continue;
 7             //This loop is essentially the same as findpairs() above.
 8             for(int j=i+1,k=num.length-1;j<k;)
 9             {
10               if(num[i]+num[j]+num[k]>0)
11               {
12                 k--;
13                 continue;
14               }
15               if(num[i]+num[j]+num[k]<0){
16                 j++;
17                 continue;
18               }
19               if(num[i]+num[j]+num[k]==0)
20               {
21                   res.add(Arrays.asList(num[i], num[j], num[k]));
22                   //不重复（内层）
23                   while (j < k && num[j] == num[k]) j++;
24                   while (j < k && num[j] == num[k]) k--;
25                   j++; k--;
26                   continue;
27               }
28            }
29         }

总结：在解决类似在数组中找给定和数对，给定和的三元组，一般都可以通过多层向少层转  最后注意：要怎样过滤掉重复的结果集

 

leet_3Sum


联系
我们