leetcode 数组+哈希+双指针+子串+滑动窗口

——————双指针

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]

class Solution {public void moveZeroes(int[] nums) {int i=0,j=0;//i 指向前面非0（即已经处理好的）的后一个位置//j 在后面找0while(i<nums.length&&nums[i]!=0){i++;}//这时nums[i]=0了j=i+1;while(j<nums.length){if(nums[j]!=0){nums[i]=nums[j];//把数移到i下标位置nums[j]=0;i++;}j++;}}
}

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

class Solution {public int maxArea(int[] height) {//双指针从两边分别开始，谁小谁移动（即尽量保留高的）int j=height.length-1;int i=0;int maxx=0,area=0;//这个最大的面积就在循环比较中得到while(i<=j){if(height[i]<=height[j]){area = (j-i)*(height[i]);i++;}else{area = (j-i)*(height[j]);j--;}if(area>maxx){maxx=area;}}return maxx;}
}

——————哈希

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

class Solution {public int[] twoSum(int[] nums, int target) {int[] results=new int[2];Map<Integer,Integer> map= new HashMap<>();for(int i=0;i<nums.length;i++){//一边遍历nums一边存入hashmapif(map.containsKey(target-nums[i])){results[0]=i;results[1]=map.get(target-nums[i]);break;}map.put(nums[i],i);}return results;}
}

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]

class Solution {public List<List<String>> groupAnagrams(String[] strs) {//key是唯一的，将单词字母排序后作为keyMap<String,List<String> > map = new HashMap<String, List<String> >();// List<String> list = new ArrayList<String>();for(String str:strs){char[] arr = str.toCharArray();Arrays.sort(arr);// String key =arr.toString();// if(map.containsKey(key)){//     list=map.get(key);// }String key = new String(arr);List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str);map.put(key,list);}return  new ArrayList<List<String>>(map.values());}
}

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

class Solution {public int longestConsecutive(int[] nums) {int result;int maxx=0;Map<Integer,Integer> map = new HashMap<>();for(int i=0;i<nums.length;i++){map.put(nums[i],0);}int a=0;for(int i=0;i<nums.length;i++){int length=0;if(!map.containsKey(nums[i]-1)){length++;a=nums[i];while(map.containsKey(a+1)){length++;a++;}}if(length>maxx){maxx=length;}}return maxx;}
}

——————普通数组

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

class Solution {public int maxSubArray(int[] nums) {int[] dp = new int [nums.length];//到i前的最大值dp[0]=nums[0];int maxx=nums[0];for(int i=1;i<nums.length;i++){dp[i]=Math.max(nums[i],dp[i-1]+nums[i]) ;maxx = Math.max(maxx,dp[i]);}return maxx;}
}

56. 合并区间

以数组 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] 可被视为重叠区间。

class Solution {public int[][] merge(int[][] intervals) {//先按[start,end]的start排序Arrays.sort(intervals,new Comparator<int[]>(){public int compare(int[] a,int[] b){return a[0]-b[0];}});List<int[]> list = new ArrayList<int[]>();int start=intervals[0][0],end=intervals[0][1];for(int i=0;i<intervals.length;i++){if(intervals[i][0]<=end){end=Math.max(end,intervals[i][1]);//哪个end更大用那个 ---注意样例[[1,4],[2,3]]}else{list.add(new int[]{start,end});start=intervals[i][0];end=intervals[i][1];}}list.add(new int[]{start,end});//最后将list转换为数组return  list.toArray(new int[list.size()][]);}
}

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

class Solution {public void rotate(int[] nums, int k) {//整体先颠倒一下，前k个再颠倒一下，后n-k个再颠倒一下if(k>nums.length) k=k%nums.length;reverse(nums,0,nums.length-1);reverse(nums,0,k-1);reverse(nums,k,nums.length-1);}void reverse(int[] nums,int l,int r){//左右下标范围int i=l,j=r;while(i<j){int tmp=nums[i];nums[i]=nums[j];nums[j]=tmp;i++;j--;}}
}

238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

class Solution {public int[] productExceptSelf(int[] nums) {//如果有个数>1的0，那全返回0//int cn=0,mul=1,mulB=1;for(int i=0;i<nums.length;i++){if(nums[i]==0){cn++;mulB=mul;}else{mulB=mulB*nums[i];}mul=mul*nums[i];}if(cn>1){Arrays.fill(nums,0);}else{for(int i=0;i<nums.length;i++){if(nums[i]==0) nums[i]=mulB;else nums[i]=mul/nums[i];}}return nums;}
}