首页 > 代码库 > leetcode 3sum

leetcode 3sum

2024-08-10 04:53:26   218人阅读

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.

 

    For example, given array S = {-1 0 1 2 -1 -4},    A solution set is:    (-1, 0, 1)    (-1, -1, 2)


使用两个标记，left和right， 对于每一个值，分别从左向右，从右向左计算

！！   如何消除duplicate 不太会！！！
public class Solution {    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {        ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();    	if(num==null||num.length<3){    		return result;    	}    	    	int sum=0;    	Arrays.sort(num);        for(int i=0;i<num.length-2;i++){            if (i != 0 && num[i] == num[i - 1]) {				continue; // to skip duplicate numbers; e.g [0,0,0,0]			}        	int left=i+1;        	int right=num.length-1;        	while(left<right){        		sum=num[i]+num[left]+num[right];        		if(sum==0){        			ArrayList<Integer> temp=new ArrayList<Integer>();        			temp.add(num[i]);        			temp.add(num[left]);        			temp.add(num[right]);        			result.add(temp);        			left++;        			right--;        			while (left < right && num[left] == num[left - 1]) { // to skip duplicates						left++;					}					while (left < right && num[right] == num[right + 1]) { // to skip duplicates						right--;					}        		}        		else if(sum<0){        			left++;        		}        		else{        			right--;        		}        	}        }                return result;    }}

　　

leetcode 3sum


联系
我们