1. 两数之和（哈希/1）
给定一个整数数组nums和一个目标整数target，请在nums中找到和为target的两个整数的数组下标，求一个时间复杂度小于O($n^2$)的算法。
假设：每组给定条件只有一个答案；不能使用相同的数组元素；2 <= nums.length <= $(10)^4$；$(-10)^9$ <= nums[i] <= $(10)^9$；$(-10)^9$ <= target <= $(10)^9$。
示例：输入：nums = [2,7,11,15], target = 9。输出：[0,1]。
【分析】
方法1：暴力法。复杂度O($n^2$)。
方法2：双指针法。先对数组排序，创建两个指针，放置在数组一头一尾，分别向中间移动，和大于target则左移右指针，和小于target则右移左指针，直到两指针相遇，可遍历整个数组，而时间复杂度为O(n)。（排序后一定不存在位置交错的解，比如10=1+9=2+8=3+7=4+6，一定是向内对称的）
方法3：哈希表法。存储互补数对应的下标的哈希表，检查互补数是否已在哈希表中。（不需要预先排序）（主要考虑这个解法，因为题意不要求数组排序）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public class Solution {
public int[] TwoSum(int[] nums, int target) {
Dictionary<int ,int> dic= new Dictionary<int,int>();
for(int i=0;i<nums.Length;i++){
int leftAmt= target-nums[i];
if(dic.ContainsKey(leftAmt)&&dic[leftAmt]!=i){
return new int[]{i, dic[leftAmt]};
}
if(!dic.ContainsKey(nums[i])){
dic.Add(nums[i],i);
}
}
return new int[]{ };
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
public class Solution{
public int[] twoSum(int[] nums, int target){
HashMap<int,int> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
int leftAmt=target-nums[i];
if(map.ContainsKey(leftAmt)){
return new int[]{map.get(leftAmt),i};
}
map.put(nums[i],i);
}
return new int[]{};
}
}
public class Solution{
public int[] twoSum(int[] nums, int target){
int[][] originNums=new int[nums.length][2];
for(int i=0;i<nums.length;i++){
originNums[i][0]=nums[i];
originNums[i][1]=i;
}
Arrays.sort(originNums,(a,b)->a[0]-b[0]);
int left=0;
int right=nums.length-1;
while(left<right){
int sum=originNums[left][0]+originNums[right][0];
if(sum==target){
return new int[]{originNums[left][1],originNums[right][1]};
}else if(sum<target){
left++;
}else{
right--;
}
}
return new int[]{0,0};
}
}
|
2. 字母异位词分组（哈希/49）
字母异位词：由重新排列源单词的所有字母得到的一个新单词。
给定一个字符串数组strs，请将字母异位词组合在一起。
假设：1<=strs.length<=$(10)^4$；0<=strs[i].length<=100；strs仅包含小写字母。
示例：输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]。输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]。
【分析】
找出由相同字母组成的单词，每种字母的个数也相同，分到一组。输出的是一个二维数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
public class Solution{
public IList<IList<string>> GroupAnagrams(string[] strs){
List<IList<string>> res=new List<IList<string>>();
Dictionary<string,IList<string>> grp=new Dictionary<string,IList<string>>();
foreach(string str in strs){
string rt=String.Concat(str.OrderBy(ch=>ch));
if(grp.ContainsKey(rt)){
grp[rt].Add(str);
}else{
grp[rt]=new List<string>{str};
}
}
foreach(string key in grp.Keys){
res.Add(grp[key]);
}
return res;
}
public IList<IList<string>> GroupAnagrams(string[] strs)
{
Dictionary<string, List<string>> dic = new Dictionary<string, List<string>>();
foreach (var str in strs)
{
char[] arr = str.ToCharArray();
Array.Sort(arr);
string key = new string(arr);
if (!dic.ContainsKey(key))
dic[key] = new List<string>();
dic[key].Add(str);
}
return new List<IList<string>>(dic.Values);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class Solution{
public List<List<string>> groupAnagrams(String[] strs){
Map<String,List<String>> ans=new HashMap<>();
for(String s:strs){
char[] ca=s.toCharArray();
Array.sort(ca);
String key=String.valueOf(ca);
if(!ans.containsKey(key)){
ans.put(key,new ArrayList<>());
}
ans.get(key).add(s);
}
return new ArrayList<>(ans.values());
}
}
|
4. 移动零（双指针/283）
给定一个数组nums，将所有0移动到数组的末尾，同时保持非零元素的相对顺序。
假设：不能复制数组；1 <= nums.length <= $(10)^4$；$(-2)^(31)$ <= nums[i] <= $2^(31)$ - 1。
示例：输入: nums = [0,1,0,3,12]，输出: [1,3,12,0,0]。
【分析】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public class Solution{
public void MoveZeroes(int[] nums){
int current=0;
for(int i=0;i<nums.Length;i++){
if(nums[i]!=0){
nums[current]=nums[i];
if(current!=i){
nums[i]=0;
}
current++;
}
}
}
}
|
5. 盛最多水的容器（双指针/11）
给定一个长度为n的整数数组heightArr，有n条垂线，第i条线的两个端点是(i,0)和(i,heightArr[i])。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水，返回容器可存储的最大水量。
【分析】
面积按最短板来求，在两个指针移动过程中求最大面积。
因为每一次都重新取最大值，所以高度数组不用提前排序。
间复杂度为 O(n)，空间复杂度为 O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public class Solution{
public int MaxArea(int[] heightArr){
int maxArea=0;
int left=0;
int right=heightArr.Length-1;
while(left<right){
int currentArea=Math.Min(heightArr[left],heightArr[right])*(right-left);
maxArea=Math.Max(maxArea,currentArea);
if(heightArr[left]<heightArr[right]){
left++;
}else{
right--;
}
}
return maxArea;
}
}
|
8. 无重复字符的最长子串（滑动窗口/3）
给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
假设：0 <= s.length <= 5 * $(10)^4$；s 由英文字母、数字、符号和空格组成。
示例：输入: s = “pwwkew”；输出: 3。（最长子串是“wke”）
【分析】
解法：滑动窗口。
这种方法的核心思想是使用两个指针来表示当前考察的子串的左右边界，并通过移动右边界来扩展子串，如果遇到重复字符，则移动左边界来缩小子串，直到重复字符被移除。在这个过程中，我们维护一个变量来记录当前无重复字符的最长子串的长度。
（1）使用HashSet作为滑动窗口。时间复杂度：O(2n) = O(n)，空间复杂度：O(min(m,n)) 。
HashSet 是一个非常有用的集合类，是基于哈希表实现的，提供了平均时间复杂度为 O(1) 的操作性能。HashSet 中的元素没有特定的顺序；集合中的元素是唯一的；添加、删除和查找操作的平均时间复杂度为 O(1)；不是线程安全的（如果在多线程环境中，可以使用Dictionary）。
（2）使用Dictionary的滑动窗口。时间复杂度：O(n)，空间复杂度：O(min(m,n)) 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class Solution{
public int LengthOfLongestSubstring(string s){
Dictionary<char,int> dic=new Dictionary<char,int>();
int result=0;
int left=0;
for(int right=0;right<s.Length;right++){
char c=s[right];
if(dic.ContainsKey(c)){
left=Math.Max(dic[c]+1,left);
}
dic[c]=right;
result=Math.Max(result,right-left+1);
}
return result;
}
}
|
10. 和为K的子数组（子串/560）
给定一个整数数组nums和一个整数k，请统计并返回该数组中和为k的子数组的个数。
子数组是数组中元素的连续非空序列。
假设：1 <= nums.length <= 2 * $(10)^4$；-1000 <= nums[i] <= 1000；$(-10)^7$ <= k <= $(10)^7$。
示例：输入：nums = [1,2,3], k = 3；输出：2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class Solution{
public int SubarraySum(int[] nums, int k){
Dictionary<int,int> prefixSum=new Dictionary<int,int>();
prefixSum[0]=1;
int count=0;
int sum=0;
for(int i=0;i<nums.Length;i++){
sum+=nums[i];
int target=sum-k;
if(prefixSum.ContainsKey(target)){
count+=prefixSum[target];
}
if(!prefixSum.ContainsKey(sum)){
prefixSum[sum]=0;
}
prefixSum[sum]++;
}
return count;
}
}
|
