1.十天通关常见算法100题(第一天)

目录

前言:

1.两数之和

2.字母异位词分组

3.最长连续序列

4.移动0

5.盛水最多的容器

6.三数之和

7.接雨水

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

9.找到字符串中所有字母异位词

10.和为K的子数组

---

前言:

纯作者做题的时候手敲的。有的题目代码，我写的可能是和常见的题解一样，有的是作者自已认为比较好理解的方法。由于是手敲，有一些是我写完copy过来的，有一些是我写完copy到做题网站的，所以会有各别题可能会有问题，如果发现请及时联系我修改，谢谢！

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]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

class Solution {public int[] twoSum(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[]{i,map.get(target-nums[i])} ;else{map.put(nums[i],i);}}return new int[]{-1,-1};}
}

2.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

• 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
• 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
• 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

class Solution {public List<List<String>> groupAnagrams(String[] strs) {List<List<String>> res = new LinkedList();Map<String,List<String>> map = new HashMap();for(String str:strs){char[] cs = str.toCharArray();Arrays.sort(cs);String s = new String(cs);if(map.containsKey(s)){map.get(s).add(str);}else{List<String> list = new LinkedList();list.add(str);map.put(s,list);}}for(String s:map.keySet()){res.add(map.get(s));}return res;}
}

3.最长连续序列

给定一个未排序的整数数组 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

示例 3：

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

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

class Solution {public int longestConsecutive(int[] nums) {if(nums.length==0||nums==null) return 0;Set<Integer> set = new HashSet();for(int num:nums){set.add(num);}int res = 0;for(int num:set){if(set.contains(num-1)) continue;int now = num;while(set.contains(now+1)){now++;}res = Math.max(res,now-num+1);}return res;}
}

4.移动0

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

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

示例 2:

输入: nums = [0]
输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

class Solution {public void moveZeroes(int[] nums) {if(nums.length==0) return ;int j = 0;for(int i=0;i<nums.length;i++){if(nums[i]!=0) nums[j++] = nums[i];}for(int i=j;i<nums.length;i++){nums[i] = 0;}}
}

5.盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

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

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

class Solution {public int maxArea(int[] height) {int l=0,r=height.length-1;int res = 0;while(l<r){res = Math.max(res,(r-l)*Math.min(height[l],height[r]));if(height[l]<height[r]){l++;}else{r--;}}return res;}
}

6.三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new LinkedList();Set<Integer> set1 = new HashSet();Set<String> set3 = new HashSet();for(int i=0;i<=nums.length-3;i++){if(!set1.contains(nums[i])){set1.add(nums[i]);int target = -nums[i];Set<Integer> set2 = new HashSet();for(int j=i+1;j<nums.length;j++){if(set2.contains(target-nums[j])){List<Integer> list = Arrays.asList(nums[i],nums[j],target-nums[j]);List<Integer> temp = list;Collections.sort(temp);String s = "";for(int num:temp){s= s+num+"_";}if(set3.contains(s)){continue;}else{res.add(list);set3.add(s);}}else{set2.add(nums[j]);}}}else{continue;}}return res;}
}

7.接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

class Solution {public int trap(int[] height) {int res = 0;Deque<Integer> q = new LinkedList();for(int i=0;i<height.length;i++){int last = 0;while(!q.isEmpty()&&height[q.getLast()]<height[i]){int top  = q.pollLast();res+= (i-top-1)*(height[top]-last);last = height[top];}if(!q.isEmpty()){res+=(i-q.getLast()-1)*(height[i]-last);}q.addLast(i);}return res;}
}

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

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

class Solution {public int lengthOfLongestSubstring(String s) {int res = 0;Map<Character,Integer> map = new HashMap();for(int l=0,r=0;r<s.length();r++){while(l<r&&map.containsKey(s.charAt(r))){map.remove(s.charAt(l++));}map.put(s.charAt(r),0);res = Math.max(res,r-l+1);}return res;}
}

9.找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

class Solution {int[] s_cnt = new int[26];int[] p_cnt = new int[26];public List<Integer> findAnagrams(String s, String p) {List<Integer> res = new LinkedList();if(s.length()<p.length()){return res;}for(int i=0;i<p.length();i++){s_cnt[s.charAt(i)-'a']++;p_cnt[p.charAt(i)-'a']++;}if(check()) res.add(0);for(int l=0,r=p.length();r<s.length();r++){s_cnt[s.charAt(r)-'a']++;s_cnt[s.charAt(l++)-'a']--;if(check()) res.add(l);}return res;}public boolean check(){for(int i=0;i<26;i++){if(s_cnt[i]!=p_cnt[i]) return false;}return true;}
}

10.和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

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

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

class Solution {public int subarraySum(int[] nums, int k) {int count = 0;for(int l=0,r=0,sum=0;r<nums.length;r++){sum += nums[r];int tempSum = sum;int tempL = l;while(tempL<=r){if(tempSum==k) count++;if(tempL<r) tempSum-=nums[tempL++];else break;}}return count;}
}