当前位置: 代码迷 >> 综合 >> 3Sum leetcode第15题 Java代码
  详细解决方案

3Sum leetcode第15题 Java代码

热度:91   发布时间:2024-01-17 06:12:01.0

直接贴上原题网址:

https://leetcode.com/problems/3sum/


思路:

先排序,将其变成一个升序序列,然后找到第一个不小于0 的元素的下标;

三个元素和为0,必然有:

第一个元素不大于0,

最后一个元素不小于0.


设定第一个元素nums[i] 从头开始,第三个元素nums[k] 从尾部开始,问题就是寻找第二个元素nums[j] 的开始位置。

if  nums[i] + nums[k] <=0;   then, j = i+1,...,k-1;

else then j = pos, ... ,k-1;

if  nums[i] + nums[k]+ nums[j] ==0, then 加入到list中


同时记录,上一次循环时的 nums[i] , nums[k] , nums[j]  ,  如果上一次循环的值与本次相同,则跳出,并进行下一次循环(continue)

如此,便可防止相同组合的加入,避免重复。


Java源代码如下:

public class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> st = new ArrayList<List<Integer>>();int lg=nums.length,pos=-1,num=0;//int[] sorted= new int[lg];for (int i=0;i<lg;i++){for (int j=i+1;j<lg;j++){if (nums[i]>nums[j]){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}}for (int i=0;i<lg;i++){if (pos==-1 && nums[i]>=0){pos = i;break;}}//System.out.println("\nlength:"+lg);int nn=pos,pre = 0,post = 0, pt;if (lg>0){pre=nums[lg-1]+1;post=nums[0]-1;}else{return st;}for (int i=0;i<=pos;i++){if (nums[i]==pre){continue;}pre = nums[i];post = nums[lg-1]+1;for (int j=lg-1;j>=pos;j--){if (nums[j] == post){continue;}post = nums[j];if (nums[i]+nums[j]==0){nn=i+1;}else if (nums[i]+nums[j]<0){nn=pos;}else{nn=i+1;}pt = nums[0]-1;for (int k=nn;k<j;k++){if (pt == nums[k]){continue;}if (nums[i]+nums[j]+nums[k]==0){List<Integer> app = new ArrayList<Integer>();    					int[] res= {nums[i], nums[k], nums[j]};for (int a=0;a<3;a++){//System.out.print(res[a]+" ");app.add(res[a]);}//System.out.println();num+=1;st.add(app);}pt = nums[k];}}}//System.out.println(num+" "+st.size());return st;}			
}



  相关解决方案