LeetCode-3SUM（数组中三数之和为0）及其 closest

傷城~ 2022-08-06 17:04 104阅读 0赞

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)

第一想法肯定是三层循环遍历的，时间复杂度O(n^3)，但是做过了了 [Two Sum][] ，感觉瞬间可解，随用hashtable的方法：

public List<List<Integer>> threeSum1(int[] num) {
            List<List<Integer>> lists = new ArrayList<>();
            HashMap<Integer, Integer> hash = new HashMap<>();
            for (int i = 0; i < num.length; i++) {
            	hash.put(num[i], i);
            }
            for (int i = 0; i < num.length; i++) {
            	for (int j = i+1; j < num.length; j++) {
            		if (hash.get(0-num[i]-num[j]) != null && num[i] <= num[j] && num[j] <= 0-num[i]-num[j]) {
            			List<Integer> list = new ArrayList<>();
            			list.add(num[i]);
            			list.add(num[j]);
            			list.add(0-num[i]-num[j]);
            			lists.add(list);
            		}
            	}
            }
            return lists;
        }

时间复杂度应该在O(n^2)，但是不幸，直接超时!看着题意，需要在O(n)解决么？经分析，肯定不行，至少也要O（NlgN）。好吧，联想起排序的复杂度，所以，看是还是先把数组给排序了比较好控制。

先上代码：

public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> lists = new ArrayList<List<Integer>>();
            if (nums == null || nums.length < 3) return lists;
            Arrays.sort(nums);
            for (int i = 0; i < nums.length-2; i++) {
                // avoid first repeat
            	if (i > 0 && nums[i] == nums[i-1]) continue;
            	int low = i+1;
            	int high = nums.length-1;
            	while (low < high) {
            		int sum = nums[i] + nums[low] + nums[high];
            		if (sum > 0) high--;
               		else if (sum < 0) low++;
            		else {
            			lists.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[low], nums[high])));
            			//avoid second repeat
            			while (low < high && nums[low] == nums[low+1]) low++;
            			low++;
            		}
            	}
            }
            return lists;
        }

先控制一个变量a，线性遍历。此时只需找出b,c满足b+c=-a即可。由于是排序好的，剩下的可以用[二分查找][Link 1]的思想找出b.c。于是求解（注意要排除重复解！！！！）

3Sum closest就相对好做许多

public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
        	int ret = nums[0]+nums[1]+nums[2];
            for (int i = 0; i < nums.length-2; i++) {
            	if (i > 0 && nums[i] == nums[i-1]) continue;
            	int low = i+1;
            	int high = nums.length-1;
            	while (low < high) {
            		int sum = nums[i] + nums[low] + nums[high];
            		if (sum > target) high--;
               		else if (sum < target) low++;
            		else return target;
            		if (Math.abs(ret-target) > Math.abs(sum-target)) ret = sum;
            	}
            }
            return ret;
        }

[Two Sum]: http://blog.csdn.net/my_jobs/article/details/43573451
[Link 1]: http://blog.csdn.net/my_jobs/article/details/43566661