数组求和

问题1

数组里求两数之和等于目标数

原理

• 这个问题可能是很多人接触LeetCode的第一道算法题了
• 解法很多种我还是喜欢使用map的方式来解决，map的key记录的是数据的元素，value记录的是数组元素对应的坐标
• 关键步骤在于 map.get(target-nums[i])!=null 说明找到元素

代码

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

注意事项

• 暂无

问题2

数组里求三数之和等于目标数

原理

• 三数之和，简单理解就是两数之和的进阶版，但是昨晚就完全不一样了。
• 第一步，对数组进行排序 arrays.sort
• 第二步，使用遍历＋二分查找的方式，搜索符合目标的元素。
• 注意两种特殊情况处理

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums == null || nums.length <= 0) {
            return list;
        }
        Arrays.sort(nums);

        for (int i = 0; i < nums.length-2; i++) {
            if (i - 1 >=0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int low = i + 1;
            int high = nums.length - 1;
            while (low < high) {
                int c = nums[i] + nums[low] + nums[high];
                if (c == 0) {
                    List<Integer> tlist = new ArrayList<>();
                    tlist.add(nums[i]);
                    tlist.add(nums[low]);
                    tlist.add(nums[high]);
                    list.add(new ArrayList<>(tlist));
                    while (low < high && nums[low] == nums[low + 1]) {
                        low++;
                    }
                    while (low < high && nums[high] == nums[high - 1]) {
                        high--;
                    }
                    low++;
                    high--;
                } else if (c < 0) {
                    low++;
                } else {
                    high--;
                }
            }

        }
        return list;
    }
}

注意事项

• 特别注意当i>=0 && nums[i] == nums[i - 1]这种重复的情况
• 注意排除掉第二种重复的情况 while (low < high && nums[low] == nums[low + 1]) 和
  while (low < high && nums[high] == nums[high - 1])

问题3

数组里求四数之和等于目标数

原理

• 原理和三数之和类似，只是多了一层循环而已，还是使用循环加双指针
• 需要特别注意边界问题

代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums==null||nums.length<=0){
            return list;
        }

        Arrays.sort(nums);

        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 low = j+1;
                int high = nums.length-1;

                while (low<high){
                    int c = nums[i]+nums[j]+nums[low]+nums[high];
                    if (c==target){
                        List<Integer> tlist = new ArrayList<>();
                        tlist.add(nums[i]);
                        tlist.add(nums[j]);
                        tlist.add(nums[low]);
                        tlist.add(nums[high]);
                        list.add(new ArrayList<>(tlist));
                        while (low<high&&nums[low]==nums[low+1]){
                            low++;
                        }
                        while (low<high&&nums[high]==nums[high-1]){
                            high--;
                        }
                        low++;
                        high--;
                    }else if(c<0){
                        low++;
                    }else{
                        high--;
                    }
                }
            }
        }
        return list;
    }
}

注意事项

• 注意第一层循环的边界问题i>0时 nums[i]==nums[i-1]
• 注意第二层循环的边界问题j>i+1时 nums[j]==nums[j+1]

问题4

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

原理

• 从三数之和到四数之和再到现在最近的三数之和，其实原理都一样，排序＋双指针
• 需要注意的是最近的三数之和，就需要有一个临时遍历记录最接近的值
• 双指针什么时候移动呢？当前的三数之和和目标数比较，小的时候low++,大的时候high--

代码

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if(nums==null||nums.length<=0){
            return -1;
        }
        Arrays.sort(nums);

        int c = Integer.MAX_VALUE;

        for(int i=0;i<nums.length;i++){
            int low = i+1;
            int high = nums.length-1;

            while(low<high){
                int t = nums[low]+nums[high]+nums[i];
                if(target==t){
                    return t;
                }
                if(Math.abs(t-target)-Math.abs(c-target)<0){
                    c = t;
                }
                if(t<target){
                    low++;
                }else{
                    high--;
                }
            }
        }
        return c;
    }
}

注意事项

• 需要注意的什么时候移动low和high