🍋1.刷题与观看须知
几数几何系列是力扣最经典的系列套题之一，它的每道题解法都非常多样化。用到了各种各样的算法知识，比如暴力枚举、哈希、排序+双指针等等。但是，虽然很多人能做出来，但是却只会一种朴素的解法，这就感到沾沾自喜了。这类题一定要会做到举一反三触类旁通，希望大家每道题都能多样化解题，同时总结出这类题的规律。
🍋2.逐步训练，鏖战力扣
🐱 1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
题目链接：两数之和https://leetcode-cn.com/problems/two-sum/
作为力扣的第一题，它是很多人成神的起点，这道题也有着自己的美丽。
题目分析：第一个想到肯定是暴力遍历，其次是利用哈希表。哈希表的解法也有不同类型，这里我们用的是Hashmap，用key存放值，value存放下标，在遍历数组nums[i]的同时寻找哈希表内是否有符合的数，有则返回两个下标，无则将nums[i]放入哈希表中。
1.暴力遍历
时间复杂度O(N^2)：使用两层for循环，最坏的情况每两个数都要被遍历几次
空间复杂度O(1)：常数级的数组空间
class Solution { public int[] twoSum(int[] nums, int target) { int n = nums.length; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (nums[i] + nums[j] == target) { return new int[]{i, j}; } } } return new int[0]; } }
2.利用HashMap
时间复杂度O(N) ：只遍历了一次数组
空间复杂度O(N)：主要为哈希表的开销
class Solution { public int[] twoSum(int[] nums, int target) { int n=nums.length; //key存放值，value存放下标 Map<Integer,Integer> map=new HashMap<>(); for(int i=0;i<n;i++){ //找到了 if(map.containsKey(target-nums[i])){ //返回下标 return new int[]{map.get(target-nums[i]),i}; } //没找到放入map中 map.put(nums[i],i); } //遍历结束仍然未找到 return new int[0]; } }
🐭2.两数之和||——输入有序数组
给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
题目链接：两数之和||——输入有序数组https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
思路分析：这道题可以同上一道一样使用暴力求解以及哈希表，但那是针对与无序数组的。因为是一个排好序的数组，我们自然要想到双指针，从两头开始遍历。当两指针相加的元素大于target，右指针向左移动，当小于target时，让左指针右移。
时间复杂度：O(n)，其中n是数组的长度，两个指针移动最多一共n次
空间复杂度：O(1)
class Solution { public int[] twoSum(int[] numbers, int target) { int n=numbers.length; int left=0; int right=n-1; while(left<right){ int count=numbers[left]+numbers[right]; //找到了，但是下标要加1，因为题目要求 if(count==target){ return new int[]{left+1,right+1}; //加起来太大了，right--，这样count会变小 }else if(count>target){ right--; //加起来太小了,left++,这样count会变大 }else{ left++; } } return new int[0]; } }
🐸3.两数之和IV——输入BST
给定一个二叉搜索树 root 和一个目标结果 k，如果树中存在两个元素且它们的和等于给定的目标结果，则返回 true。
题目链接：两数之和 IV - 输入 BSThttps://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/
题目分析:这道题与前面的两数之和类似，只不过是元素存放的形式变成了树，我们同样可以利用Hashset来遍历树。
方法：Hashset加遍历树。判断当前root时，set中是否存在k-root.val，如果存在直接返回true。不存在的话将此时的root.val存放进set中，同时去左子树和右子树中继续查找。
时间复杂度O(n)，n为节点的数量，最坏的情况下，整棵树被遍历一次
空间复杂度O(n)，最坏的情况下，set存储n个节点的值。
class Solution { public boolean findTarget(TreeNode root, int k) { Set<Integer> set=new HashSet<>(); return find(root,k,set); } public boolean find(TreeNode root,int k,Set set){ //如果root为空直接返回false if(root==null) return false; if(set.contains(k-root.val)){ return true; } //这个没找到就加入到set集合中 set.add(root.val); //同时去左子树和右子树查找 return find(root.left,k,set)||find(root.right,k,set); } }
🐶4.三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
题目链接：三数之和https://leetcode-cn.com/problems/3sum/
题目分析：这道题和两数之和看上去类似，但做法却不相同，难度也不在一个档次，朴素暴力的做法再最后几个例子会超时
方法1：朴素暴力（超时）
时间复杂度O(N^3)
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); int n=nums.length; List<List<Integer>> list=new ArrayList<>(); for(int i=0;i<n-2;i++){ for(int j=n-1;j>i+1;j--){ int x=i+1; while(x<j){ int count=nums[i]+nums[x]+nums[j]; if(count==0){ List<Integer> arr=new ArrayList<>(); arr.add(nums[i]); arr.add(nums[x]); arr.add(nums[j]); if(!list.contains(arr)){ list.add(arr); } x++; }else if(count>0){ break; }else{ x++; } } } } return list; } }
