nSum问题解法集合

痛定思痛。 2022-10-30 01:23 135阅读 0赞

/** * 2Sum问题 * 输入一个数组nums和一个整数target，可以保证数组中存在两个数的和为target，返回所有和为target的元素对。 */
    public class Test1 { 
    
        public static void main(String[] args) { 
            int[] nums = new int[]{ 1,3,1,2,2,3};
            int target = 5;
            List<Integer[]> res = threeSum(nums, target);
            for (Integer[] re : res) { 
                System.out.println(re[0] + "," + re[1] + "," + re[2]);
            }
        }
    
        /** * 暴力解法 */
        static List<Integer[]> twoSum(int[] nums, int target) { 
            List<Integer[]> res = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) { 
                for (int j = i + 1; j < nums.length; j++) { 
                    if (nums[j] + nums[i] == target) { 
                        res.add(new Integer[]{ i, j});
                    }
                }
            }
            return res;
        }
    
        /** * 使用Map减少时间复杂度 */
        static List<Integer[]> twoSum2(int[] nums, int target) { 
            List<Integer[]> res = new ArrayList<>();
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) { 
                map.put(nums[i], i);
            }
            for (int i = 0; i < nums.length; i++) { 
                int other = target - nums[i];
                if (map.containsKey(other) && map.get(other) != i) { 
                    res.add(new Integer[]{ i, map.get(other)});
                }
            }
            return res;
        }
    
        /** * 先排序，再双指针 */
        static List<Integer[]> twoSum3(int[] nums, int target) { 
            List<Integer[]> res = new ArrayList<>();
            // 先排序
            quickSort(nums, 0, nums.length - 1);
            // 双指针
            int left = 0;
            int right = nums.length - 1;
            while (left < right) { 
                int sum = nums[left] + nums[right];
                if (sum == target) { 
                    res.add(new Integer[]{ nums[left], nums[right]});
                    left++;
                    right--;
                } else if (sum < target) { 
                    left++;
                } else { 
                    right--;
                }
            }
            return res;
        }
    
        /** * 先排序，再双指针 * 去掉重复的元素对 */
        static List<Integer[]> twoSum4(int[] nums, int target){ 
            List<Integer[]> res = new ArrayList<>();
            // 先排序
            quickSort(nums, 0, nums.length - 1);
            // 双指针
            int left = 0;
            int right = nums.length - 1;
            while (left < right) { 
                int leftVal = nums[left];
                int rightVal = nums[right];
                int sum =  leftVal + rightVal;
                if (sum == target) { 
                    res.add(new Integer[]{ leftVal, rightVal});
                    while (left < right && nums[left] == leftVal) left++;
                    while (left < right && nums[right] == rightVal) right--;
                } else if (sum < target) { 
                    while (left < right && nums[left] == leftVal) left++;
                } else { 
                    while (left < right && nums[right] == rightVal) right--;
                }
            }
            return res;
        }
    
        /** * 如果是求3sum问题，可以先穷举第一个值，然后其余两个值得sum用2sum方案来解决 */
        static List<Integer[]> threeSum(int[] nums, int target) { 
            quickSort(nums, 0, nums.length-1);
            List<Integer[]> res = new ArrayList<>();
            int n = nums.length;
            for (int i = 0; i < nums.length; i++) { 
                List<Integer[]> tuples = twoSum5(nums, i + 1, target-nums[i]);
                for (Integer[] tuple : tuples) { 
                    tuple[0] = nums[i];
                    res.add(tuple);
                }
                while (i < n-1 && nums[i] == nums[i+1]) i++;
            }
            return res;
        }
    
        static List<Integer[]> twoSum5(int[] nums, int start, int target){ 
            List<Integer[]> res = new ArrayList<>();
            // 双指针
            int left = start;
            int right = nums.length - 1;
            while (left < right) { 
                int leftVal = nums[left];
                int rightVal = nums[right];
                int sum =  leftVal + rightVal;
                if (sum == target) { 
                    res.add(new Integer[]{ 0, leftVal, rightVal});
                    while (left < right && nums[left] == leftVal) left++;
                    while (left < right && nums[right] == rightVal) right--;
                } else if (sum < target) { 
                    while (left < right && nums[left] == leftVal) left++;
                } else { 
                    while (left < right && nums[right] == rightVal) right--;
                }
            }
            return res;
        }
    
    
        /** * 快排 */
        static void quickSort(int[] nums, int start, int end) { 
            if (nums.length == 0 || start >= end) { 
                return;
            }
            int left = start;
            int right = end;
            int key = nums[left];
            while (left < right) { 
                //如果key右边的数一直大于key，那么一直往左查询
                while (left < right && nums[right] >= key) { 
                    right--;
                }
                // 把小于key的这个值填入到索引为left这个坑里
                if (left < right) { 
                    nums[left] = nums[right];
                }
                // 然后开始找比key小的值，如果key左边的值一直小于key，那么一直往右边找
                while (left < right && nums[left] <= key) { 
                    left++;
                }
                //找到这个比key大的值，填到right这个坑里
                if (left < right) { 
                    nums[right] = nums[left];
                }
                //这个时候，left这个坑就空出来了，然后就把key放到这个空出来的坑里
                nums[left] = key;
            }
            // 递归查找
            quickSort(nums, right + 1, end);
            quickSort(nums, start, left - 1);
        }
    
    }