A Java Solution with Two Pointers


  • 4
    H
     public List<List<Integer>> fourSum(int[] nums, int target) {
        	List<List<Integer>> result = new ArrayList<List<Integer>>();
        	if (nums == null || nums.length < 4) {
        		return result;
        	}
        	Arrays.sort(nums);
        	for (int i = 0; i < nums.length - 3; i ++) {
        		for (int j = i + 1; j < nums.length - 2; j ++) {
        			int head = j + 1;
        			int tail = nums.length - 1;
        			while (head < tail) {
        				int tempSum = nums[i] + nums[j] + nums[head] + nums[tail];
        				if (tempSum == target) {
        					List<Integer> item = new ArrayList<Integer>();
        					item.add(nums[i]);
        					item.add(nums[j]);
        					item.add(nums[head]);
        					item.add(nums[tail]);
        					if (result.contains(item) == false) {
        						result.add(item);
        					} 
        					head ++;
        					tail --;
        				} else if (tempSum < target) {
        					head ++;
        				} else {
        					tail --;
        				}
        			}
        		}
        	}
        	return result;
        }

  • 1
    J

    if you skip calculation when nums[i] == nums[i-1] and nums[j] == nums[j-1],
    you needn't call list.contains method, you just compare the last elements in results is OK.


  • 0
    D

    I doubt this is correct. contains(Object o) will always return true in this solution, because even if with same values, the two lists are different objects.


  • 0
    N

    you can have a try before doubt. it works in practice.


  • 0
    Y

    this is right , you can see the source of code in JDK . Actually, the method contains(Object o) invoke method equals(Object ) for each element in List. Then the method equals(Object ) in List will check every element in List to return the result, which means it does't only check whether the object is same.
    this is the source code

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;
    
        ListIterator<E> e1 = listIterator();
        ListIterator e2 = ((List) o).listIterator();
        while (e1.hasNext() && e2.hasNext()) {
            E o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        return !(e1.hasNext() || e2.hasNext());
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.