一、Array

两数之和（#1）

TODO 只有一个有效答案，可进阶实现_ 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 示例1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
示例2：
输入：nums = [3,3,4,15], target = 7
输出：TODO 是否考虑要满足条件的第一个数值 [0,2] or [1,2]

// 返回值
public static int[] twoSumGetValue(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(nums[0], 0);
    for (int i = 1; i < nums.length; i++) {
        if (map.containsKey(target - nums[i])) {          
            return new int[]{target - nums[i], nums[i]};   
        }       
        map.put(nums[i], i);  
    }
        return new int[]{-1, -1};
    }
// 返回索引
public static int[] twoSumGetIndex(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i])) {
            return new int[]{map.get(target - nums[i]), i};
        }
    // 处理：{3, 3, 11, 15} target：6 的情况 因为 map 会覆盖相同的key的内容，放在后面 put 就不需要考虑这一点了 ！！！
            map.put(nums[i], i);
    }
    return new int[]{-1, -1};
}

三数之和（#15）

给你一个包含 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] 输出：[]

前提：

sum > target -> right—
sum < target -> left++
left >= right -> 结束内循环i++ left = i + 1
判断核心数是否重复
判断左右指针是否重复

�代码：

private static List<List<Integer>> threeSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    // 快速排序
    Arrays.sort(nums);
    // 定义当前循环的num[i] 为核心匹配对象     
    for (int i = 0; i < nums.length; i++) {
        // 如果核心大于targetNumbe 则结束循环     
        if (nums[i] > target) break;
        // 第二次循环后，判断设置的核心数是否与上一个重复  
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1;         
        int right = nums.length - 1;
        // 只要左右不重叠，就继续移动指针 
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];           
            if (sum == target) {           
                result.add(Arrays.asList(nums[i], nums[left], nums[right]))   
                left++;
                right--;
                // 移动时left与前一个重复了，则继续移动
                while (left < right && nums[left] == nums[left - 1]) {                           left++;              
                }
                while (right > left && nums[right] == nums[right + 1]) {                         right--;            
                }
            } else if (sum > target) {               
                right--;             
            } else {                   
                left++;            
            }          
        }    
    }      
    return result; 
}

复杂度分析：

时间复杂度依然为O(n^2)
空间复杂度仅为常数级O(1)

下一个子序列（#31）

时间复杂度：O(n)

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。
如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。
必须原地修改，只允许使用额外常数空间。

示例 1：输入：nums = [1,2,3] 输出：[1,3,2]

示例 2：输入：nums = [3,2,1] 输出：[1,2,3]

示例 3：输入：nums = [1,1,5] 输出：[1,5,1]

提示： 1 <= nums.length <= 100 0 <= nums[i] <= 100

思路：

代码:

public static void nextPermutation(int[] nums) {
        // 从后往前遍历找到第一个k < k+1 的位置
        int k = nums.length - 2;
        while (k >= 0 && nums[k] >= nums[k + 1])
            k--;
        // 如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）
        if (k < 0) {
            convert(nums, 0, nums.length -1);
        }
        int i = k + 2;
        while (i < nums.length && nums[i] > nums[k])
            i++;
        int temp = nums[k];
        nums[k] = nums[i-1];
        nums[i - 1] = temp;
        // 1，5，8，6，（7，4，4，3，1）处理最后的排序（确保只是更大的下一个排列） 因为已经是降序
        convert(nums, k + 1, nums.length -1);
    }
    private static void convert(int[] nums, int start, int end) {
        while (start < end) {
            int temp2 = nums[start];
            nums[start] = nums[end];
            nums[end] = temp2;
            start++;
            end--;
        }
    }

二、Find查找

搜索二维矩阵（#74）

TODO 返回索引

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。<br />该矩阵具有如下特性：s

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

示例1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13
输出：false
示例 3：
输入：matrix = [], target = 0
输出：false

提示：
m == matrix.length
n == matrix[i].length
0 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
int[][] nums = {
{1, 3, 5, 7},
{10, 11, 16, 20},
{23, 30, 34, 50}
}; �

先假设将二维数组转换成一个一维数组
此时 index = x * n + y
x = index / n（列）
y = index % n（列）

代码：�

// 时间复杂度：Olog(m*n) 空间复杂度：O(1)
    public static boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        int col = matrix[0].length;
        if (row == 0) return false;
        int left = 0;
        int right = row * col -1;
        while (left <= right) {
            int midIdx = (left + right) / 2;
            int midValue = matrix[midIdx / col][midIdx % col]; // --> index = x * n + y
            if (midValue < target) {
                left = midIdx + 1;
            } else if (midValue > target) {
                right = midIdx - 1;
            } else {
                System.out.println(midIdx + " x: " + midIdx / col + " y: " + midIdx % col);
                return true;
            }
        }
        return false;
    }

寻找重复数（#287）

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。
你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：输入：nums = [1,3,4,2,2] 输出：2

示例 2：输入：nums = [3,1,3,4,2] 输出：3

进阶：

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

实现方法：

hashMap
hashSet
快慢指针法

快慢指法：
这是一种比较特殊的思路。把nums看成是顺序存储的链表，nums中每个元素的值是下一个链表节点的地址。
那么如果nums有重复值，说明链表存在环，本问题就转化为了找链表中环的入口节点，因此可以用快慢指针解决。

比如数组：
[3，6，1，4，6，6，2]
示例：

整体思路如下：

第一阶段，寻找环中的相遇节点
- 初始时，都指向链表第一个节点nums[0]；
- 慢指针每次走一步，快指针走两步；
- 如果有环，那么快指针一定会再次追上慢指针；相遇时，相遇节点必在环中
第二阶段，寻找环的入口节点（重复的地址值）
- 重新定义两个指针，让before，after分别指向链表开始节点，相遇节点
- before与after相遇时，相遇点就是环的入口节点

代码：

public int findDuplicate(int[] nums) {
    int low = 0;
    int fast = 0;
    do {
        low = nums[low];
        fast = nums[nums[fast]];
    } while (low != fast);
    int before = 0;
    int after = fast;
    while (before != after){
        before = nums[before];
        after = nums[after];
    }
    return  before;
}