4Sum

本来以为只要在3Sum外面再包一层循环就好了，可是。。。在Judge Large的时候还是超时了 呜呜呜

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> tempList;
        for (int i = 0; i < num.length - 3; ++i)
            for (int j = i + 1; j < num.length - 2; ++j){
                int tempTarget = target - num[i] - num[j];
                int m = j + 1;
                int n = num.length - 1;
                while (m < n){
                    if (num[m] + num[n] > tempTarget)
                        n--;
                    else if (num[m] + num[n] < tempTarget)
                            m++;
                        else {
                            tempList = new ArrayList<Integer>();
                            Collections.addAll(tempList, num[i], num[j], num[m], num[n]);
                            if (!results.contains(tempList))
                                results.add(tempList);
                            m++;
                            n--;
                        }
                }
            }
        return results;
    }
}

。。。。居然还有可能超时可能不超时的情况。。。囧 多run了几次就过了 汗啊 去google上找找答案好了

额 似乎没有什么其他好的方法了
倒是发现了两个小问题：
1、Java中ArrayList的contains方法
我没有重写contains方法，但是为什么ArrayList判断contrains的时候，明明是两个不同的ArrayList，只是里面的数都一样，这样就判断相等了？
了解了 contains中使用到了equals方法，然后ArrayList的equals方法是比较他们是不是相等而不是看对象指针是不是一样~~
2、搜索结果中提到了brute-force方法，可是这和简单模式匹配有什么关系呢？

评论

1 楼 superich2008 2012-11-14  

1、去重可以用Set集合
2、在排序后，相邻2个元素如果相同可以减少一次循环（在多重循环中效率更高）

public static java.util.List<java.util.List<Integer>> fourSum(int[] nums, int sum)
	{
		final int n = nums.length;
		if (n < 4)
			return java.util.Collections.emptyList();
		
		// 排序
		java.util.Arrays.sort(nums);
		
		java.util.Set<java.util.List<Integer>> set = new java.util.HashSet<java.util.List<Integer>>();
		// i j k m 为数组下标
		int i = 0, j = i + 1, k = j + 1, m = n - 1;
		for (i = 0; i < n; i++)
		{
			if (i > 0 && nums[i] == nums[i - 1]) 
			{
				continue;
			}
			for (j = i + 1; j < n; j++)
			{
				if (j > i + 1 && nums[j] == nums[j - 1])
				{
					continue;
				}
				k = j + 1;
				m = n - 1;
				while (k < m)
				{
					if (k > j + 1 && nums[k] == nums[k - 1])
					{
						k++;
						continue;
					}
					int t = nums[i] + nums[j] + nums[k] + nums[m];
					if (t == sum)
					{
						java.util.List<Integer> temp = new java.util.ArrayList<Integer>();
						java.util.Collections.addAll(temp,
								Integer.valueOf(nums[i]),
								Integer.valueOf(nums[j]),
								Integer.valueOf(nums[k]),
								Integer.valueOf(nums[m]));
						set.add(temp);
						k++;
						m--;
					} else if (t > sum)
					{
						m--;
					} else
					{
						k++;
					}
				} // end-while
			} // end-for
		} // end-for
		return new java.util.ArrayList<java.util.List<Integer>>(set);
	}