(1)LC1-两数之和
描述：寻找数组中的两个数使其和为给定值target，一个数不能使用两次，每组输入只有一个唯一答案
思路：
方法1：排序+双指针，O(NlogN)时间，空间O(1)
方法2：set，O(N)时间，空间O(N)
(2)LC11-盛最多水的容器
描述：给一个数组，表示横坐标上的点的高度，求能容纳最多水的体积
思路：双指针
从两头开始，移动高度更低的指针，因为移动高度更高的指针容纳的水只能更少
(3)LC15-三数之和
描述：给一个数组，找出数组内的所有三元组(a, b, c)，使得a+b+c为0；每个元素只能使用一次，结果不能包含重复三元组
思路：排序+双指针
外层循环枚举第一个数a，去重：if(i>0 && nums[i]==nums[i-1]) continue;
内层循环使用双指针枚举b、c，去重：当得到一组b、c符合条件时，跳过所有相同的b和c，然后b++，c—
(4)LC16-最接近的三数之和
描述：给一个数组和一个目标值target，找出数组内所有三元组(a,b,c)，使得三元组的和与target最接近，返回三元组的和，每个元素只能使用一次，每组输入只有唯一答案
思路：排序+双指针
只有唯一结果，不需要考虑去重
设置全局minDiff变量，全局minDiffSum
minDiff表示和target的最小差值，minDiffSum表示和target最小差值的三元组的和
外层循环枚举a，内层用双指针枚举b、c，内层搜索，三元组和小于target则left++，大于taget则right—，
每组(a,b,c)都更新全局minDiff和minDiffSum，当搜索到三元组和等于target时直接返回target
(5)LC18-四数之和
描述：给一个数组和一个目标值target，找出数组中所有的四元组(a, b, c, d)，使得四元组的和等于target，每个元素只能使用一次，结果不能包含重复四元组
方法：排序+双指针
三层循环，外面两层分别枚举a、b，里面一层双指针枚举c、d
去重：外面两层去重 “ if(i>0 && nums[i]==nums[i-1]) continue;”
最内层去重”当得到一组c、d符合条件时，跳过所有相同的c和d，然后c++，d—“
(6)LC26-删除有序数组的重复项
描述：给一个有序数组，请原地删除重复元素，使得每个元素只出现一次，返回删除后的数组长度
思路：原地重建
index为原数组下一个待插入的位置，初始化index=1(第一个元素肯定不会重复）
扫描原数组所有元素(foreach)，如果当前扫描元素num不等于nums[index-1]则将num插入到index位置，并index++，否则跳过当前扫描元素
扫描完毕返回index
(7)LC27-移除元素
描述：给一个数组和一个值val，原地移除所有数值等于val的元素，并返回移除后数组的新长度
方法：原地重建
index为原数组下一个待插入的位置，初始化index=0，
扫描数组所有元素，当前元素num不等于val时，
num插入到index位置且index++
扫描完毕返回index
(8)LC31-下一个排列
描述：给一个数组，求将数组重新按照字典序排列的下一个更大的排列，如果不存在下一个更大的排列，就将数组按照升序排列，要求空间O(1)
思路：倒序扫描
目标就是把右边的较大的数和左边的较小的数交换
从右往左搜索第一个位置x，使得nums[x]
将[x,n-1]位置区间的元素从左到右升序排序，双指针左右交换即可，
因为[x+1, n-1]位置的元素必然从左到右降序排列
(9)LC33-搜索旋转排序数组
描述：升序无重复元素数组nums，在某个点上旋转了，比如[4,5,6,0,1,2]，
寻找nums中是否存在目标值target
思路：二分搜索
原始区间[left, right]被mid分成两部分，判断出有序的那部分，就可以O(1)判断target是否在有序这部分，从而排除一半搜索空间
while(left<=right)，因为是搜索某个值，所以left<=right
比如nums[left]<=nums[mid]则[left, mid]有序
(10)LC34-排序数组查找target出现的第一个位置和最后一个位置
思路：二分搜索
第一个位置：
mid位置元素等于target，也要将搜索区间向左偏，high—；
退出循环后 low位于第一个位置，high位于第一个位置左边
最后一个位置：
mid位置元素等于target时，也要将搜索区间向右偏，low++;
退出循环后 high位置位于最后一个位置，low位于最后位置右边
需要检测是否nums[low]或nums[high]等于target，因为可能输入数组无有效结果
需要检测low、high是否下标溢出：
比如寻找第一个元素nums=[2,2], target=3，low上溢出
比如寻找最后一个元素，nums=[3,3]，target=2，high下溢出
(11)LC35-搜索插入位置
描述：给一个无重复元素排序数组和一个目标值target，在数组中找到目标值，并返回其索引。如果目标值不存在，返回按顺序插入的位置
思路：二分搜索
搜索数组 “大于等于target” 的第一个位置
nums[mid]>target时：high = mid - 1;
nums[mid]
(12)LC39-组合总和
描述：给定一个无重复元素的正整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合，candidates 中的数字可以无限制重复被选取，要求解集不能包含重复的组合
思路：回溯
方法1：回溯+递归
public void combinationSum(int idx, int[] candidates, int target, List<List<Integer>> res, List<Integer> current){if(target==0){res.add(new ArrayList<>(current));return;}if(target<0 || idx>=candidates.length){return;}current.add(candidates[idx]);// 重复选择,下次选择还是从 idx 位置开始combinationSum(idx, candidates, target-candidates[idx], res, current);current.remove(current.size()-1);combinationSum(idx+1, candidates, target, res, current);}
方法2：回溯+递归+循环
public void combinationSum(int idx, int[] candidates, int target, List<List<Integer>> res, List<Integer> current){
if(target==0){
res.add(new ArrayList<>(current));
return;
}
if(target<0 || idx>=candidates.length){
return;
}
for(int i=idx;i<candidates.length;i++){
current.add(candidates[i]);
// 重复选择, 下次选择还是从 i 位置开始
combinationSum(i, candidates, target-candidates[i], res, current);
current.remove(current.size()-1);
}
}
(13)LC40-组合总和 II
描述：给定一个正整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合，candidates 中的数字在每个组合只能使用一次，要求解集不能包含重复的组合
思路：回溯
要去重，所以要排序
方法1：回溯+递归+排序+去重
public void combinationSum2(int idx, int target, int[] candidates, List<List<Integer>> res, List<Integer> current) {
// 递归+回溯, 全组合时必须在叶子节点时才将当前组合加入全局结果集, 否则有重复
if(idx == candidates.length && target==0){
res.add(new ArrayList<>(current));
return;
}
if(target<0 || idx>= candidates.length){
return;
}
// 当前组合选择 idx 位置元素
current.add(candidates[idx]);
combinationSum2(idx+1, target-candidates[idx], candidates, res, current);
current.remove(current.size()-1);
// 有重复元素时, 且前面被选择了则后面必须被选择
if(idx>0 && candidates[idx]==candidates[idx-1] && current.size()>0 &¤t.get(current.size()-1)==candidates[idx]){
return;
}
// 当前组合不选择 idx 位置元素
combinationSum2(idx+1, target, candidates, res, current);
}
方法2：回溯+递归+循环+排序+去重
public void combinationSum2(int idx, int target, int[] candidates, List<List<Integer>> res, List<Integer> current) {
if(target==0){
res.add(new ArrayList<>(current));
}
if(target<0){
return;
}
for(int i=idx;i<candidates.length;i++){
// 跳过同层, 不跳过同树枝
if(i>idx && candidates[i]==candidates[i-1]){
continue;
}
current.add(candidates[i]);
combinationSum2(i+1, target-candidates[i], candidates, res, current);
current.remove(current.size()-1);
}
}
(14)LC45-跳跃游戏 II
描述：给一个非负整数数组，最初位于数组的0位置，数组中的每个元素的值代表你在该位置可以跳跃的最大长度，目标是用最少的跳跃次数到达数组的最后一个位置，返回所需的最少跳跃次数。
思路：贪心
方法1：
从n-1位置，反向推导，每次寻找能一次跳到目标位置targetPos的位置i，要求i离target尽可能远
设targetPos=n-1，从0位置开始向右遍历，若i+nums[i]>=target则更新targetPos为i，step++，当targetPos为0时停止遍历
方法2：
从0位置开始，正向推导，每次寻找从当前位置currentPos能一次跳到的位置y，且y能到达尽可能远
维护跳跃次数step，当前轮结束位置endPos，当前轮最远位置maxPos，遍历每个位置时更新maxPos，当遍历到endPos时，令endPos=maxPos，step++，遍历到n-2位置时结束，因为endPos初始为0，0位置就跳跃了一次，n-1位置若刚好等于最后一轮的endPos会多出一次跳跃
(15)LC48-旋转图像
描述：矩阵顺时针旋转90度，要求空间O(1)
思路：两次翻转
顺时针旋转90度：
先水平翻转：
然后主对角线翻转：
联立1.水平翻转，2.主对角线翻转：
(16)LC53-最大子序和
描述：给一个整数数组nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
思路：动态规划
设为以位置结尾的最大和连续子数组，则
(16)LC54-螺旋矩阵
描述：给你一个m行n列的矩阵 matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素。
思路：模拟
方法1：模拟螺旋
向右->向下->向左->向上->向右，注意记录被访问过的位置，不要重复访问
方法2：按层模拟
外层到内层
设：左上角 (topX, topY)，右下角 (bottomX, bottomY)
每圈对上边、右边、下边、左边的四条边依次遍历：
上边：i=[topY,bottomY]的[topX,i] 加入结果集
右边：i=[topX+1, bottomX] [i, bottomY]加入结果集
topX
左边：i=[bottomX-1, topX+1], [i, topY] 加入结果集
若有收获，就点个赞吧
0 人点赞
