LeetCode 3无重复字符的最长子串、LeetCode 56合并区间、LeetCode 15三数之和、LeetCode 55跳跃游戏

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

题目描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

一、使用set的滑动窗口法（一次遍历，节省了重复遍历），左指针下表标i，右指针从-1开始，for第一个先计算r，之后再if(i!=0)先删除remove左元素，再添加右元素，ans=Math.max(ans, ans.size())（后一个ans是新ans） 二、while循环中，满足不包含且不越界，先进行r+1，然后再改变r的值 三、set的remove（i！=0的时候进行）、add（i从0到n都可以）需要参数为元素值 可执行完整代码：

public int lengthOfLongestSubstring(String s) {
        Set set = new HashSet<>();   // 哈希集合，记录每个字符是否出现过
        int n = s.length();
        int r = -1, ans = 0;   // 右指针，初始值为 -1，for循环首先执行while从r+1开始添加
        for (int i = 0; i < n; i++) {
            if (i != 0) {   // 左指针先remove，再不断移动右指针
                set.remove(s.charAt(i - 1));
            }
            while (r < n && r + 1 < n && !set.contains(s.charAt(r + 1))) {
                set.add(s.charAt(r + 1));   // 先r+1，再++（如果r+1满足，就让r变为r+1）
                ++r;
            }
            ans = Math.max(ans, set.size());
        }
        return ans;
    }

LeetCode 56合并区间（排序，一次循环比较0右1左 或 0右1右）（排序时间复杂度nlogn）

题目描述：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

一、首先按照第一个数组元素升序：重写Arrays.sort中的new Comparator，return o1[0]-o2[0]；其次顺序遍历排序后数组，从第二个开始将上一个数组右元素（ans.size()-1）[1]与本次i数组左元素进行比较，如果<就添加，否则（else）上一个数组右元素[1]=max（上一次的[1]，i[1]） 二、注意最后结果要List.toArray()转为数组，List使用size、add、get 完整代码：

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][2];
        Arrays.sort(intervals, new Comparator() {   // 直接Arrays.sort()就可以对数组进行修改
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];   // 谁在右边谁大：o2[0]大的顺序
            }
        });
        List ans = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int left = intervals[i][0], right = intervals[i][1];
            if (ans.size() == 0 || ans.get(ans.size() - 1)[1] < left) {   // 首一维数组or区间不交叉的数组
                ans.add(intervals[i]);
            } else {
                ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], right);
            }
        }
        return ans.toArray(new int[ans.size()][2]);   // List转数组
    }

LeetCode 15三数之和（时间复杂度n2，空间复杂度） 一、首先判断长度小于等于2返回ans，然后排序 二、之后for循环遍历一遍，第一次i=0有target，之后从left=i+1，right=length-1开始和target做比较，while循环，去重；后面i>0的时候判断nums[i]== nums[i-1]去重continue 三、找到相等的使用ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));来添加元素进ans 完整代码：

public List> threeSum(int[] nums) {
        List> ans = new ArrayList<>();
        if (nums == null || nums.length <= 2) return ans;

        Arrays.sort(nums);   // 排序nlogn

        for (int i = 0; i < nums.length; i++) {   // 时间复杂度n2
            if (nums[i] > 0) break;   // 第一个数大于0，后面两个数都大于0，此次循环肯定不成立了
            if (i > 0 && nums[i] == nums[i - 1]) continue;   // 去重
            int target = -nums[i];
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
                    left++;right--;   // target一定，改变left肯定也要改变right，否则另一个数和上一次的一样了
                    while (left < right && nums[left] == nums[left - 1]) left++;   // 去重
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return ans;
    }

LeetCode 55跳跃游戏

题目描述：
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。
示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

一、维护位置i所能跑到的最远下标，使用rightMost = Math.max(rightMost, i + nums[i]);更新；外层for循环i=0 - n-1，内层if(i<=rightMost)的时候进行判断>=nums.length-1

以题目中的示例一
[2, 3, 1, 1, 4]
为例：

我们一开始在位置 00，可以跳跃的最大长度为 22，因此最远可以到达的位置被更新为 22；

我们遍历到位置 11，由于 1 leq 21≤2，因此位置 11 可达。我们用 11 加上它可以跳跃的最大长度 33，将最远可以到达的位置更新为 44。由于 44 大于等于最后一个位置 44，因此我们直接返回 True。

完整代码：

public boolean canJump(int[] nums) {
        int rightMost = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i <= rightMost) {   // 首元素满足0=0   // 遍历下标为i位置
                rightMost = Math.max(rightMost, i + nums[i]);   // rightMost为max（上一次最大，i+nums[i]），即i位置所能跑的最远距离
                if (rightMost >= nums.length - 1) return true;
            }
        }
        return false;
    }