3Sum 4Sum_JAVA_编程开发_程序员俱乐部

3Sumclass="date" title="2012-01-18 01:33:00" style="margin: 0px 10px 0px 0px; padding: 0px; border: 0px; font-size: 10px; vertical-align: baseline; background-color: transparent; color: #999999; float: right;">Jan 18 '129830 / 38290

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)

?

?

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        int len = num.length;
        
        int key,k ,m,sum;
        Integer preKey = Integer.MIN_VALUE;
        Integer preLastStart = Integer.MIN_VALUE;
        for(int i = 0;i<=len-3;i++){
            k = i+1;
            m = len-1;
            key = 0-num[i];
            if(key!=preKey||k>preLastStart){//remove the duplicate when start to find match two Sum
                preKey = key;
               
                Integer preInnerOk = Integer.MIN_VALUE;
                while(k<m){
                    sum = num[k]+num[m];
                    if(sum > key) m--;
                    else if(sum < key) k++;
                    else {
                        if(num[k]!=preInnerOk){// remove the duplicate inner two sum
                            ArrayList<Integer> result = new ArrayList<Integer>();
                            result.add(num[i]);
                            result.add(num[k]);
                            result.add(num[m]);
                            resultList.add(result);
                            preInnerOk = num[k];
                        }
                        preLastStart = k;
                        k++;
                       
                    }
                }
            }
        }
        return resultList;
    }
}

?

?

Run Status:?Wrong Answer Progress:?25/28?test cases passed.

Showing the first failed test case.

?

input output expected ? [-2,0,0,2,2] [[-2,0,2],[-2,0,2]] [[-2,0,2]] ? Run Status:?Wrong Answer

?monospace, 'Courier New', Courier; line-height: 15px;">

Progress:?26/28?test cases passed.

Showing the first failed test case.

?

input output expected ? [-1,0,1,2,-1,-4] [[-1,0,1]] [[-1,-1,2],[-1,0,1]] ?

?

Run Status:?Wrong Answer Progress:?25/28?test cases passed.

Showing the first failed test case.

?

input output expected ? [1,-1,-1,0] [[-1,0,1],[-1,0,1]] [[-1,0,1]] ? ? ? ? ?

?

Run Status:?Wrong Answer Progress:?27/28?test cases passed.

Showing the first failed test case.

?

input output expected ? [0,0,0,0] [[0,0,0],[0,0,0]] [[0,0,0]] ? Run Status:?Accepted!
Program Runtime:?760 milli secs Progress:?311/311?test cases passed.