Lexi's Leetcode solutions

Archive for October 18th, 2013

和3sum一样,多加一维就多n的复杂度,这个是O(n^3),没看到别人有什么好的做法。注意防止duplicate的地方都标红了,算是比较简洁的two pointers防止dup的方式,以后可以都这么些。

    public ArrayList<ArrayList> fourSum(int[] num, int target) {
    	ArrayList<ArrayList> result = new ArrayList<ArrayList>();
    	Arrays.sort(num);
    	for (int i = 0; i < num.length; i++) {     		
                if (i > 0 && num[i] == num[i - 1])
    			continue;
    		for (int j = i + 1; j < num.length; j++) {     			
                        if (j > i + 1 && num[j] == num[j - 1] ) //一开始写的j > 0,就把1111 x=4的组合给漏掉了
    				continue;
    			int p = j + 1, q = num.length - 1;
    			while (p < q) {
    				int sum = num[i] + num[j] + num[p] + num[q];
    				if (sum == target) {
    					ArrayList quad = new ArrayList();
    					quad.add(num[i]);
    					quad.add(num[j]);
    					quad.add(num[p]);
    					quad.add(num[q]);
					result.add(quad);
					do {p++;} while (p < q && num[p] == num[p - 1]);
					do {q--;} while (p < q && num[q] == num[q + 1]);
    				} else if (sum < target) {
    					p++;
    				} else {
    					q--;
    				}
    			}
    		}
    	}
    	return result;
    }

本来以为是弱智题,但是要求不能duplicate之后,发现代码还真不好写了。难怪通过率只有16%这么低。

  • 如何处理“和上一个一样就不要做了”这种duplicate情况?(形成自己的代码习惯)
    • if (i > 0 或类似condition && num[i] == num[i – 1]) continue;
    • 这样可以保证永远笼罩在while (some condition)的保证之下,用continue就不会出现越界等情况。
    • 如果是递归,外层没有while,则用while (boundary &&  num[i] == num[i – 1[) {i++;}
public ArrayList<ArrayList> threeSum(int[] num) {
    ArrayList<ArrayList> result = new ArrayList<ArrayList>();
    Arrays.sort(num);
    for (int i = 0; i < num.length; i++) { 			
        if (i > 0 && num[i] == num[i - 1])
            continue;
	int x = 0 - num[i];
	int p = i + 1, q = num.length - 1;
	while (p < q) {
            if (p > i + 1 && num[p] == num[p - 1]) {
                p++;
                continue;
            }
            if (q < num.length - 1 && num[q] == num[q + 1]) {
                q--;
                continue;
            }
	    if (num[p] + num[q] == x) {
                ArrayList triple = new ArrayList();
		triple.add(num[i]);
		triple.add(num[p]);
		triple.add(num[q]);
		result.add(triple);
	    } else if (num[p] + num[q] < x) {
		p++;
	    } else {
	        q--;
	    }
	}
    }
    return result;
}

Blog Stats

  • 221,510 hits
October 2013
M T W T F S S
 123456
78910111213
14151617181920
21222324252627
28293031