問題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

數組里求四數之和等于目標數

原理

• 原理和三數之和類似，只是多了一層循環(huán)而已，還是使用循環(huán)加雙指針
• 需要特別注意邊界問題

代碼

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;
    }
}

注意事項

• 注意第一層循環(huán)的邊界問題i>0時 nums[i]==nums[i-1]
• 注意第二層循環(huán)的邊界問題j>i+1時 nums[j]==nums[j+1]

問題4

給定一個包括 n 個整數的數組 nums 和 一個目標值 target。找出 nums 中的三個整數，使得它們的和與 target 最接近。返回這三個數的和。假定每組輸入只存在唯一答案。

原理

• 從三數之和到四數之和再到現(xiàn)在最近的三數之和，其實原理都一樣，排序＋雙指針
• 需要注意的是最近的三數之和，就需要有一個臨時遍歷記錄最接近的值
• 雙指針什么時候移動呢？當前的三數之和和目標數比較，小的時候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