1. 两数之和

方法一：最暴力的方法，两层 for 循环遍历判断，时间复杂度：O( n2 )
由于需要返回的是数组的下标，因此并不能对数组进行排序，再二分查找进行优化。
方法二：利用「哈希表可以快速判断元素是否在集合中」的特点，进行优化

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ints = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (target == nums[i] + nums[j]) {
                    ints[0] = i;
                    ints[1] = j;
                    return ints;
                }
            }
        }
        return ints;
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {

        {
            /*
            这种写法错误的原因：如果有两个值相同的元素，则先加入 HashMap 的会被覆盖，从而造成结果错误
            因此需要在元素加入 HashMap 前进行判断
             */
        }

        int[] result = new int[2];

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hashMap.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int value = target - nums[i];
            Integer integer = hashMap.get(value);
            if (integer != null && integer != i) {
                result[0] = i;
                result[1] = integer;
            }
        }

        return result;
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {

        int[] result = new int[2];
        // key 为数组值，value 为数字值对应的下标 index
        HashMap<Integer, Integer> hashMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            Integer index = hashMap.get(target - nums[i]);
            if (index != null) {
                result[0] = i;
                result[1] = index;
            }
            hashMap.put(nums[i], i);
        }

        return result;
    }
}

2. 两数相加

3. 无重复字符的最长子串

4. 寻找两个正序数组的中位数

5. 最长回文子串

class Solution {
    public String longestPalindrome(String s) {

        String result = "";

        if (s.length() == 1) {
            return s;
        }

        for (int i = 0; i < s.length() - 1; i++) {
            for (int j = i; j < s.length(); j++) {
                String subStr = judge(s, i, j);
                if (subStr != null && subStr.length() > result.length()) {
                    result = subStr;
                }
            }
        }
        return result;
    }

    // 判断字符串 s 下标从[startIndex, endIndex]构成的字符串是否为回文串
    // 如果是回文串则返回回文串，否则返回null
    public String judge(String s, int startIndex, int endIndex) {

        int start = startIndex;
        int end = endIndex;

        while (start < end) {
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                return null;
            }
        }
        return s.substring(startIndex, endIndex + 1);
    }
}

7. 整数反转

8. 字符串转换整数 (atoi)

10. 正则表达式匹配

11. 盛最多水的容器

13. 罗马数字转整数

14. 最长公共前缀

15. 三数之和

17. 电话号码的字母组合

class Solution {

    String[] strs = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    List<String> results = new ArrayList<>();
    StringBuilder result = new StringBuilder();

    String digits;

    public List<String> letterCombinations(String digits) {
        if (digits.length() > 0) {
            this.digits = digits;
            backtracking(0);
        }
        return results;
    }

    // s 代表集合的起始元素 [s...9]
    public void backtracking(int index) {
        if (index >= digits.length()) {
            results.add(result.toString());
            return;
        }
        int number = digits.charAt(index) - '0';
        String str = strs[number];
        for (int i = 0; i < str.length(); i++) {
            result.append(str.charAt(i));
            backtracking(index + 1);
            result.deleteCharAt(result.length() - 1);
        }
    }
}

20. 有效的括号

栈在括号匹配中的应用

class Solution {
    public boolean isValid(String s) {

        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if ('(' == s.charAt(i)) {
                stack.push(')');
            } else if ('[' == s.charAt(i)) {
                stack.push(']');
            } else if ('{' == s.charAt(i)) {
                stack.push('}');
            } else {
                if (!stack.empty()) {
                    Character element = stack.pop();
                    if (element != s.charAt(i)) {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        return stack.empty();

    }
}

21. 合并两个有序链表

22. 括号生成

23. 合并K个升序链表

26. 删除有序数组中的重复项

27. 移除元素

class Solution {
    public int removeElement(int[] nums, int val) {

        {
            /*
            如果 nums[fast] == val，则 fast++
            如果 nums[fast] != val，则 nums[slow] = nums[fast] 并且 slow++ fast++

            时间复杂度：O(n)
            空间复杂度：O(1)
             */
        }

        // 指向下一个将要赋值的位置
        int slow = 0;
        // 指向当前将要处理的位置
        int fast = 0;

        while (fast < nums.length) {
            if (nums[fast] == val) {
                fast++;
            } else {
                nums[slow] = nums[fast];
                slow++;
                fast++;
            }
        }
        return slow;
    }
}

双指针优化
如果要移除的元素恰好在数组的开头，
例如序列 [1, 2, 3, 4, 5]，当 val 为 1 时，我们需要把每一个元素都左移一位。
注意到题目中说：「元素的顺序可以改变」。
实际上我们可以直接将最后一个元素 5 移动到序列开头，取代元素 1，得到序列 [5,2,3,4]，
同样满足题目要求。这个优化在序列中 val 元素的数量较少时非常有效。

class Solution {
    public int removeElement(int[] nums, int val) {

        {
            /*
            如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，
            然后右指针 right 左移一位。如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来，直到左指针指向的元素的值不等于 val 为止。

            当左指针 left 和右指针 right 重合的时候，左右指针遍历完数组中所有的元素。

            时间复杂度：O(n)
            空间复杂度：O(1)
             */
        }

        int slow = 0;
        int fast = nums.length - 1;

        while (slow <= fast) {
            if (nums[slow] == val) {
                nums[slow] = nums[fast];
                fast--;
            } else {
                slow++;
            }
        }
        return slow;
    }
}

28. 实现 strStr()

29. 两数相除

33. 搜索旋转排序数组

34. 在排序数组中查找元素的第一个和最后一个位置

36. 有效的数独

38. 外观数列

39. 组合总和

class Solution {

    List<List<Integer>> results = new ArrayList<>();
    List<Integer> result = new ArrayList<>();
    int[] candidates;
    int target;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        this.target = target;
        backtracking(0, 0);
        return results;
    }

    // sum 为 result 所有元素的和
    // 子集合为区间 [startIndex, candidates.length - 1] 的元素
    public void backtracking(int sum, int startIndex) {
        if (sum == target) {
            results.add(new ArrayList<>(result));
            return;
        } else if (sum > target) {
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            result.add(candidates[i]);
            backtracking(sum + candidates[i], i);
            result.remove(result.size() - 1);
        }
    }
}

class Solution {

    List<List<Integer>> results = new ArrayList<>();
    List<Integer> result = new ArrayList<>();
    int[] candidates;
    int target;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        {
            /*
            在求和问题中，排序之后再剪枝是常见的套路
             */
        }

        Arrays.sort(candidates);
        this.candidates = candidates;
        this.target = target;
        backtracking(0, 0);
        return results;
    }

    // sum 为 result 所有元素的和
    // 子集合为区间 [startIndex, candidates.length - 1] 的元素
    public void backtracking(int sum, int startIndex) {
        if (sum == target) {
            results.add(new ArrayList<>(result));
            return;
        } else if (sum > target) {
            return;
        }

        for (int i = startIndex; i < candidates.length && (sum + candidates[i]) <= target; i++) {
            result.add(candidates[i]);
            backtracking(sum + candidates[i], i);
            result.remove(result.size() - 1);
        }
    }
}

40. 组合总和 II

难点：需要树层去重。

class Solution {

    List<List<Integer>> results = new ArrayList<>();
    List<Integer> result = new ArrayList<>();
    int[] candidates;
    boolean[] used;
    int target;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        {
            /*
            在求和问题中，排序之后再剪枝是常见的套路
             */
        }
        Arrays.sort(candidates);
        this.used = new boolean[candidates.length];
        this.candidates = candidates;
        this.target = target;
        backtracking(0, 0);
        return results;
    }

    // sum 为 result 所有元素的和
    // 子集合为区间 [startIndex, candidates.length - 1] 的元素
    public void backtracking(int sum, int startIndex) {
        if (sum == target) {
            results.add(new ArrayList<>(result));
            return;
        } else if (sum > target) {
            return;
        }

        for (int i = startIndex; i < candidates.length && (sum + candidates[i]) <= target; i++) {
            if (i > 0 && candidates[i - 1] == candidates[i] && used[i - 1] == false) {
                continue;
            } else {
                result.add(candidates[i]);
                used[i] = true;
            }
            backtracking(sum + candidates[i], i + 1);
            result.remove(result.size() - 1);
            used[i] = false;
        }
    }
}

45. 跳跃游戏 II

class Solution {

    int[] nums;
    int minTime = Integer.MAX_VALUE;

    public int jump(int[] nums) {
        this.nums = nums;
        backtracking(0, 0);
        return minTime;
    }

    /**
     * @param time  到达数组的 index 下标，跳跃次数
     * @param index 达到的下标
     */
    public void backtracking(int time, int index) {
        if (index == nums.length - 1) {
            if (time < minTime) {
                minTime = time;
            }
        }

        for (int i = 1; i <= nums[index] && (index + i < nums.length); i++) {
            backtracking(time + 1, index + i);
        }
    }
}

class Solution {
    public int jump(int[] nums) {

        // dp[i] 的含义为：跳跃到数组下标为 index 的位置上,最少的跳跃次数为 dp[i]
        int[] dp = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j <= nums[i] && i + j < nums.length; j++) {
                if (dp[i + j] == 0) {
                    dp[i + j] = dp[i] + 1;
                } else {
                    dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
                }
            }
        }
        return dp[nums.length - 1];
    }
}

46. 全排列

排列问题需要一个 used 数组，标记已经选择过的元素。

class Solution {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] nums;
    // 排列问题需要一个 used 数组，标记已经选择过的元素
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        this.used = new boolean[nums.length];
        backtracking();
        return result;
    }

    public void backtracking() {
        if (path.size() == nums.length ) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if(used[i] == true) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backtracking();
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

47. 全排列 II

排列问题需要一个 used 数组，标记已经选择过的元素。
该 used 数组也用于解决树层去重问题。

class Solution {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] nums;
    // 排列问题需要一个 used 数组，标记已经选择的元素
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        this.used = new boolean[nums.length];
        backtracking();
        return result;
    }

    public void backtracking() {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i] == true) {
                continue;
            }
            if ( i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backtracking();
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

51. N 皇后

class Solution {

    List<List<String>> result = new ArrayList<>();
    char[][] chessBoard;
    int n;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        // 用 . 初始化棋盘
        this.chessBoard = new char[n][n];
        for (int i = 0; i < chessBoard.length; i++) {
            Arrays.fill(chessBoard[i], '.');
        }
        backtracking(0);
        return result;
    }

    public void backtracking(int row) {
        if (row == n) {
            List<String> strList = constructStrList();
            result.add(strList);
            return;
        }

        for (int i = 0; i < n; i++) {
            boolean valid = isValid(row, i);
            if (!valid) {
                continue;
            }
            chessBoard[row][i] = 'Q';
            backtracking(row + 1);
            chessBoard[row][i] = '.';
        }

    }

    public List<String> constructStrList() {
        List<String> strings = new ArrayList<>();
        for (char[] chars : chessBoard) {
            strings.add(new String(chars));
        }
        return strings;
    }

    // 判断该位置能否放置皇后
    // i 为行, j 为列
    public boolean isValid(int i, int j) {

        // 判断同一列
        for (int k = 0; k < i; k++) {
            if (chessBoard[k][j] == 'Q') {
                return false;
            }
        }

        // 判断对角线
        int a = i - 1;
        int b = j - 1;
        while (a >= 0 && b >= 0) {
            if (chessBoard[a][b] == 'Q') {
                return false;
            } else {
                a--;
                b--;
            }
        }

        int c = i - 1;
        int d = j + 1;
        while (c >= 0 && d < n) {
            if (chessBoard[c][d] == 'Q') {
                return false;
            } else {
                c--;
                d++;
            }
        }

        return true;
    }
}

55. 跳跃游戏

class Solution {

    int[] nums;
    int flage = 0;
    // 备忘录, 记录已经处理过的子问题
    int[] memo;

    public boolean canJump(int[] nums) {
        this.nums = nums;
        this.memo = new int[nums.length];

        backtracking(0);

        return flage == 1;
    }

    public void backtracking(int curIndex) {
        if (memo[curIndex] == 1) {
            return;
        }
        if (curIndex == nums.length - 1) {
            flage = 1;
            return;
        }

        for (int i = 1; i <= nums[curIndex]; i++) {

            if (flage == 1) {
                break;
            }

            int temp = curIndex + i;
            if (temp < nums.length) {
                backtracking(temp);
                memo[temp] = 1;
            }
        }
    }
}

class Solution {
    public boolean canJump(int[] nums) {

        int maxIndex = 0;

        for (int i = 0; i < maxIndex && i < nums.length; i++) {
            int temp = i + nums[i];
            if (temp > maxIndex) {
                maxIndex = temp;
            }
        }

        if (maxIndex >= nums.length - 1) {
            return true;
        } else {
            return false;
        }
    }
}

56. 合并区间

思路：

1. 先将区间按照左端点排序（只能按照左端点排序，不能按照右端点排序，因为存在后面区间左端点较小的情况，例如：[2, 3],[4, 5], [1,10] 这种）

2. 然后遍历区间并更新可合并区间的最大右端点，如果这个区间不能和之前的区间合并了，那么就提交之前的区间，并将这个区间作为新的区间，重复更新操作。

   class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        });
   
        List<int[]> result = new ArrayList<>();
   
        int l = intervals[0][0];
        int r = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= r && intervals[i][1] > r) {
                r = intervals[i][1];
            } else if(intervals[i][0] > r) {
                result.add(new int[]{l, r});
                l = intervals[i][0];
                r = intervals[i][1];
            }
        }
        result.add(new int[]{l, r});
   
        int[][] results = new int[result.size()][2];
        result.toArray(results);
   
        return results;
    }
   }
   

   59. 螺旋矩阵 II

   有思路，不写了。
   方法：遵循「循环不变量」思想，按层模拟。

   62. 不同路径

66. 加一

69. x 的平方根

70. 爬楼梯

73. 矩阵置零

75. 颜色分类

76. 最小覆盖子串

77. 组合

class Solution {

    List<List<Integer>> results = new ArrayList<>();
    List<Integer> result = new ArrayList<>();
    int n;
    int k;

    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        backtracking(1);
        return results;
    }

    // s 代表集合的起始元素 [s...n]
    public void backtracking(int s) {
        if (result.size() == k) {
            results.add(new ArrayList<>(result));
        }

        for (int i = s; i <= n; i++) {
            result.add(i);
            i += 1;
            backtracking(i);
            i -= 1;
            result.remove(result.size() - 1);
        }
    }
}

class Solution {

    List<List<Integer>> results = new ArrayList<>();
    List<Integer> result = new ArrayList<>();
    int n;
    int k;

    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        backtracking(1);
        return results;
    }

    // s 代表集合的起始元素 [s...n]
    public void backtracking(int s) {
        if (result.size() == k) {
            results.add(new ArrayList<>(result));
        }

        // 剪枝
        for (int i = s; i <= n && ((n - i + 1) + result.size() >= k); i++) {
            result.add(i);
            i += 1;
            backtracking(i);
            i -= 1;
            result.remove(result.size() - 1);
        }
    }
}

78. 子集

class Solution {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        backtracking(0);
        return result;
    }

    // 集合的区间范围 [startIndex, nums.length - 1]
    public void backtracking(int startIndex) {
        result.add(new ArrayList<>(path));
        if (startIndex >= nums.length) {
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            backtracking(i + 1);
            path.remove(path.size() - 1);
        }
    }
}

79. 单词搜索

84. 柱状图中最大的矩形

88. 合并两个有序数组

90. 子集 II

class Solution {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    int[] nums;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        this.nums = nums;
        this.used = new boolean[nums.length];
        backtracking(0);
        return result;
    }

    // 集合的区间范围 [startIndex, nums.length - 1]
    public void backtracking(int startIndex) {
        result.add(new ArrayList<>(path));
        if (startIndex >= nums.length) {
            return;
        }

        for (int i = startIndex; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtracking(i + 1);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

91. 解码方法

94. 二叉树的中序遍历

98. 验证二叉搜索树