【刷题】LeetCode刷题汇总

一、刷题

记录LeetCode力扣刷题

题号1：两数之和

1. 双循环（暴力解法）：

class Solution {public int[] twoSum(int[] nums, int target) {int[] list=new int[2];for(int i=0; i<nums.length;i++){for(int j=i+1; j<nums.length;j++){if(nums[i]+nums[j]==target){list[0]=i;list[1]=j;}}}return list;}
}

时间复杂度O(n²)，j的初始值如果为0的话，循环次数会更多且需判断 i!=j

2. HashMap 唯一key

class Solution {public int[] twoSum(int[] nums, int target) {int[] list=new int[2];Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (hashMap.containsKey(target - nums[i])) {list[0]=hashMap.get(target - nums[i]);list[1]=i;}hashMap.put(nums[i], i);}return list;}
}

我拿到题目时也想过先确定第一个数，再判断第二数是否在数组中（避免嵌套循环），但是第一时间没找到合适方法，后面看官方解法才想到。官方解法没有提前生成list数组，能提高一点执行用时。

3. 双指针（未通过版）：排序后下标已经乱了，不适合该题但是思路可以

class Solution {public int[] twoSum(int[] nums, int target) {int[] list=new int[2];int start=0,end=nums.length-1;QuickSort(nums,start,end);// Arrays.sort(nums);while(start<end){if(nums[start]+nums[end]>target) end--;if(nums[start]+nums[end]<target) start++;if(nums[start]+nums[end]==target){list[0]=start;list[1]=end;break;}}return list;}public void QuickSort(int[] nums,int start,int end){if(start<end){// 获取分区后的枢纽位置int pivotIndex=Partition(nums,start,end);// 分别对枢纽左右两边的子数组进行递归排序QuickSort(nums, start, pivotIndex - 1);QuickSort(nums, pivotIndex + 1, end);}}public int Partition(int[] nums,int start,int end){// 单边循环int pivot=nums[start]; // 基准元素int mask=start; // 标记指针for(int i=start+1;i<=end;i++){if(nums[i]<nums[mask]){mask++;// 交换int temp=nums[i];nums[i]=nums[mask];nums[mask]=temp;}}// 交换基准 nums[start]=nums[mask];nums[mask]=pivot;return mask;}}

先使用快速排序（或者Arrays.sort()）排序好，再用首尾指针去判断，时间复杂度O(nlog₂n)（取决于排序算法O(n)+O(nlog₂n)=O(nlog₂n)）

二、解法总结

1. 嵌套循环

暴力解法最常用，不考虑时间复杂度

2. 双指针

首尾指针，在排序的基础上使用，避免嵌套循环