【LeetCode】查找表问题：几数和系列问题

谁践踏了优雅 2022-10-29 09:11 152阅读 0赞

### 查找典例 ###

*  几数之和通常先排序，然后外层有 n - 2 个循环，对剩余两个元素用对撞指针
    
     *  排序的目的是为了方便确定这个元素是否被 i j 使用过，因为如果每种情况唯一的话，此时就会满足 num\[i\] <= nums\[j\] <= nums\[k\] ，就可以轻易判断对 k 的选择是否会导致重复（因为 k 是 O(1) 查找得到，而非遍历得到）
     *  对于有序数组，对撞指针可以轻松确定出和为某值的位置，而且避免了从查找表获得元素时，还需要判断元素大小与等于情况下的个数
 *  总结：就两种方法，最内两层对撞指针，或者最内一层查找表 + 范围与个数判断

#### [1. 两数之和][1.] ####

难度简单10247收藏分享切换为英文接收动态反馈

给定一个整数数组 `nums` 和一个整数目标值 `target`，请你在该数组中找出 **和为目标值** 的那 **两个** 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

**示例 1：**

输入：nums = [2,7,11,15], target = 9
    输出：[0,1]
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

**示例 2：**

输入：nums = [3,2,4], target = 6
    输出：[1,2]

**题解**

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            Map<Integer , Integer> record = new HashMap<>();
            for(int i = 0 ; i < nums.length ; i ++){ 
                record.put(nums[i] , i);
            }
            
            int[] res = new int[2];
            for(int i = 0 ; i < nums.length ; i ++){ 
                if(record.get(target - nums[i]) != null && record.get(target - nums[i]) != i){ 
                    res[0] = i;
                    res[1] = record.get(target - nums[i]);
                    return res;
                }
            }
    
            return res;
        }
    }

#### [15. 三数之和][15.] ####

难度中等2945收藏分享切换为英文接收动态反馈

给你一个包含 `n` 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 \*a，b，c ，\*使得 *a + b + c =* 0 ？请你找出所有和为 `0` 且不重复的三元组。

\*\*注意：\*\*答案中不可以包含重复的三元组。

**示例 1：**

输入：nums = [-1,0,1,2,-1,-4]
    输出：[[-1,-1,2],[-1,0,1]]

**示例 2：**

输入：nums = []
    输出：[]

**示例 3：**

输入：nums = [0]
    输出：[]

**题解**

class Solution { 
        public List<List<Integer>> threeSum(int[] nums) { 
            Arrays.sort(nums);
            Map<Integer , Integer> record = new HashMap<>();
    
            for(int i = 0 ; i < nums.length ; i ++){ 
                record.put(nums[i] , record.getOrDefault(nums[i] , 0) + 1);
            }
    
            List<List<Integer>> res = new LinkedList<>();
            for(int i = 0 ; i < nums.length ; i ++){ 
                if(nums[i] > 0){ 
                    break;
                }
                if(i > 0 && nums[i] == nums[i - 1]){ 
                    continue;
                }
    
                for(int j = i + 1; j < nums.length ; j ++){ 
                    if(j > i + 1 && nums[j] == nums[j - 1]){ 
                        continue;
                    }
    
                    int target = 0 - nums[i] - nums[j];
                    // nums[j] >= nums[i];
                    if(target < nums[j]){ 
                        break;
                    }
    
                    Integer d = record.get(target);
                    // targetNow >= nums[j]，要验证如果等于与连等的情况
                    if(d != null){ 
                        int times = nums[i] == target && nums[j] == target ? 2 : nums[i] == target || nums[j] == target ? 1 : 0 ;
                        if(d > times){ 
                            res.add(Arrays.asList(nums[i] , nums[j] , target)); 
                        }
                    }
                }
            }
    
            return res;
        }
    }

#### [18. 四数之和][18.] ####

难度中等739收藏分享切换为英文接收动态反馈

给定一个包含 *n* 个整数的数组 `nums` 和一个目标值 `target`，判断 `nums` 中是否存在四个元素 \*a，\**b，c* 和 *d* ，使得 *a* \+ *b* \+ *c* \+ *d* 的值与 `target` 相等？找出所有满足条件且不重复的四元组。

**注意：**

答案中不可以包含重复的四元组。

**示例：**

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
    
    满足要求的四元组集合为：
    [
      [-1,  0, 0, 1],
      [-2, -1, 1, 2],
      [-2,  0, 0, 2]
    ]

**回溯：超时**

class Solution { 
        List<List<Integer>> res;
        public List<List<Integer>> fourSum(int[] nums, int target) { 
            Arrays.sort(nums);
    
            res = new LinkedList<>();
            boolean[] bitmap = new boolean[nums.length];
            for(int i = 0 ; i < nums.length ; i ++){ 
                if(i > 0 && nums[i] == nums[i - 1]){ 
                    continue;
                }
                func(nums , i , target , 4 , bitmap);
            }
    
            return res;
        }
    
        void func(int[] nums , int idx , int target  , int nodes , boolean[] bitmap){ 
            if(nodes <= 0){ 
                return;
            }
            bitmap[idx] = true;
    
            if(nums[idx] == target && nodes == 1){ 
                Integer[] thisRes = new Integer[4];
                for(int i = 0 , resIdx = 0 ;i < nums.length ; i++){ 
                    if(bitmap[i]){ 
                        thisRes[resIdx ++] = nums[i];
                    }
                }
                res.add(Arrays.asList(thisRes));
                bitmap[idx] = false;
                return;
            }
    
            for(int i = idx + 1 ; i < nums.length ; i ++){ 
                if(i > idx + 1 && nums[i] == nums[i - 1]){ 
                    continue;
                }
                
                int nextTarget = target - nums[idx];
                if(nums[i] >= 0 &&  nextTarget < nums[i]){ 
                    break;
                }
                func(nums , i , nextTarget , nodes - 1 , bitmap);
            }
    
            bitmap[idx] = false;
        }
    }

**最快 O(n3)**

class Solution { 
        public List<List<Integer>> fourSum(int[] nums, int target) { 
            Arrays.sort(nums);
            List<List<Integer>> res = new LinkedList<>();
    
            for(int i = 0 ; i  < nums.length ; i ++){ 
                if(i > 0 && nums[i] == nums[i - 1]){ 
                    continue;
                }
    
                for(int j = i + 1; j < nums.length ; j ++){ 
                    if(j > i + 1 && nums[j] == nums[j - 1]){ 
                        continue;
                    }
    
                    int targetNow = target - nums[i] - nums[j] ;
                    int l = j + 1 , r = nums.length - 1;
    
                    while(l < r){ 
                        if(l > j + 1  && nums[l] == nums[l - 1]){ 
                            l ++;
                            continue;
                        }
                        if(nums[l] + nums[r] == targetNow) { 
                            res.add(Arrays.asList(nums[i] , nums[j] , nums[l] ,nums[r]));
                        }
                        
                        if(nums[l] + nums[r] <= targetNow){ 
                            l ++;
                        }else { 
                            r --;
                        }
                    }
                }
            }
    
            return res;
        }
    
        
    }

#### [16. 最接近的三数之和][16.] ####

难度中等681收藏分享切换为英文接收动态反馈

给定一个包括 *n* 个整数的数组 `nums` 和 一个目标值 `target`。找出 `nums` 中的三个整数，使得它们的和与 `target` 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

**示例：**

输入：nums = [-1,2,1,-4], target = 1
    输出：2
    解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

**题解**

*  几数和问题的正确简便做法应该还是双指针。

class Solution { 
        public int threeSumClosest(int[] nums, int target) { 
            int res = 99999;
    
            TreeMap<Integer ,Integer> record = new TreeMap<>();
            for(int i = 0 ; i < nums.length ; i ++){ 
                record.put(nums[i] , record.getOrDefault(nums[i] , 0) + 1);
            }
    
            for(int i = 0 ;i < nums.length ; i ++){ 
                for(int j = i + 1 ; j < nums.length ; j ++){ 
                    int targetNow = target - nums[i] - nums[j];
    
                    if(record.get(targetNow) != null){ 
                        int times = nums[i] == targetNow && nums[j] == targetNow ? 2 : nums[i] == targetNow || nums[j] == targetNow ? 1 : 0;
                        if(record.get(targetNow) > times){ 
                            return target;
                        }
                    }
    
                    Integer lower = targetNow;
                    while(true){ 
                        lower = record.lowerKey(lower);
                        if(lower == null){ 
                            break;
                        }
    
                        int times = nums[i] == lower && nums[j] == lower ? 2 : nums[i] == lower || nums[j] == lower ? 1 : 0;
                        if(record.get(lower) > times){ 
                            int now = target -(targetNow - lower);
                            res = Math.abs(target - now) < Math.abs(target - res) ? now : res;
                            break;
                        }
                    }
    
                    Integer higher = targetNow;
                    while(true){ 
                        higher = record.higherKey(higher);
                        if(higher == null){ 
                            break;
                        }
    
                        int times = nums[i] == higher && nums[j] == higher ? 2 : nums[i] == higher || nums[j] == higher ? 1 : 0;
                        if(record.get(higher) > times){ 
                            int now = target -(targetNow - higher);
                            res = Math.abs(target - now) < Math.abs(target - res) ? now : res;
                            break;
                        }
                    }
                }
            }
    
            return res;
        }
    
    }

[1.]: https://leetcode-cn.com/problems/two-sum/
[15.]: https://leetcode-cn.com/problems/3sum/
[18.]: https://leetcode-cn.com/problems/4sum/
[16.]: https://leetcode-cn.com/problems/3sum-closest/