讨论/《中级算法》 - 三数之和/
《中级算法》 - 三数之和

用哈希表的话主要是去重操作不好想

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        //排序方便去重
        Arrays.sort(nums);
        //记录每个数的下标
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        for(int i = 0; i < n; ++i) {
            hashMap.put(nums[i], i);
        } 
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for(int i = 0; i < n; ++i) {
            int target = -nums[i];
            //去重
            if(i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            for(int j = i + 1; j < n; ++j) {
                //去重
                if(j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                Integer index = hashMap.get(target - nums[j]);
                //看存不存在target
                if(index != null && index > j) {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], target - nums[j])));
                }
            }
        }
        return res;
    }
}
1
展开全部 18 讨论