.經(jīng)典題目
1.求二數(shù)之和:https://leetcode-cn.com/problems/two-sum/
思路：
使用hashMap首启，將遍歷過(guò)的值放入其中，進(jìn)行比較；
時(shí)間復(fù)雜度 n
空間負(fù)責(zé)度 1
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[]{map.get(target-nums[i]),i};
}
map.put(nums[i],i);
}
return new int[]{-1,-1};
}
}
- 求三數(shù)之和：https://leetcode-cn.com/problems/3sum/
1.特殊情況：對(duì)于數(shù)組長(zhǎng)度n,如果數(shù)組為null或者長(zhǎng)度小于3，返回[]
2.對(duì)數(shù)組進(jìn)行排序线得；
3.遍歷排序后數(shù)組：
a.若num[i]>0,后面不可能再有等于0的情況，直接返回
b.對(duì)于重復(fù)元素裸扶，跳過(guò)框都，避免出現(xiàn)重復(fù)解；
c.左指針L=i+1呵晨，右指針R=n-1,當(dāng)L<R 時(shí)魏保，執(zhí)行循環(huán)
當(dāng)num[i]+num[L]+num[R]==0,執(zhí)行循環(huán)，判斷左邊界和右邊界是否和下一位重復(fù)摸屠，去除重復(fù)谓罗；
若和大于0，R左移季二，注意去重
若和小于0檩咱，L右移，注意去重
image.png
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> lists=new ArrayList<>();
if(nums==null|| nums.length<3){
return lists;
}
//排序
Arrays.sort(nums);
//雙指針
int len=nums.length;
for(int i=0;i<len;i++){
if(nums[i]>0) {
return lists;
}
if(i>0 && nums[i]==nums[i-1]){
continue;
}
int cur=nums[i];
int L=i+1;
int R=len-1;
while(L<R){
int tmp=cur+nums[L]+nums[R];
if(tmp==0){
List<Integer> list=new ArrayList<>();
list.add(cur);
list.add(nums[L]);
list.add(nums[R]);
lists.add(list);
while(L<R &&nums[L+1]==nums[L]){
L++;
}
while(L<R && nums[R-1]==nums[R]){
R--;
}
L++;
R--;
}else if(tmp <0){
L++;
}else{
R--;
}
}
}
return lists;
}
}
3.求眾數(shù):https://leetcode-cn.com/problems/majority-element/
摩爾投票法思路
候選人(cand_num)初始化為num[0]胯舷，票數(shù)count初始化為1
當(dāng)遇到與cand_num相同的數(shù)刻蚯，則票數(shù)count++，否則票數(shù)count--
當(dāng)票數(shù)count為0時(shí)桑嘶，更好候選人炊汹，并將票數(shù)count重置為1
遍歷完數(shù)組后，cand_num即為最終答案
原理：
投票法是遇到相同的則票數(shù)+1,遇到不同的則票數(shù)-1
且多數(shù)元素的個(gè)數(shù)>n/2
其余元素的個(gè)數(shù)總和<=n/2
因此多數(shù)元素的個(gè)數(shù)-其余元素的個(gè)數(shù)總和>=1
時(shí)間復(fù)雜度n
空間復(fù)雜度1
class Solution {
public int majorityElement(int[] nums) {
int cand_num=nums[0];
int count=1;
for(int i=1;i<nums.length;i++){
if(cand_num==nums[i]){
count++;
}else if(count-- == 0){
cand_num=nums[i];
count = 1;
}
}
return cand_num;
}
}
4.求缺失的第一個(gè)正數(shù)：https://leetcode-cn.com/problems/first-missing-positive/
有一個(gè)前提：n個(gè)數(shù)組成的數(shù)組逃顶，那么最小正整數(shù)的范圍一定在[1,n+1]之間
由于題目要求我們”只能使用常數(shù)級(jí)別的空間“讨便，因此我們可以把原始的數(shù)組當(dāng)做哈希表來(lái)使用。abstract
要找的數(shù)在[1,n+1],n+1不用找以政，前面元素找不到的時(shí)候霸褒，我們才返回n+1
思路:把1放在下標(biāo)為0的地方，2放在坐標(biāo)為1的地方
時(shí)間復(fù)雜度 n (while不會(huì)每次都循環(huán)盈蛮，之多循環(huán)n次)
空間復(fù)雜度 1
public class Solution {
public int firstMissingPositive(int[] nums) {
int len=nums.length;
for(int i=0;i<len;i++){
//重點(diǎn)nums[nums[i]-1]!=nums[i],為啥不是num[i]!=i+1,這樣對(duì)重復(fù)的數(shù)字會(huì)造成死循環(huán)
while(nums[i]>0&&nums[i]<=len&&nums[nums[i]-1]!=nums[i]){
swap(nums,nums[i]-1,i);
}
}
for(int i=0;i<len;i++){
if(nums[i]!=i+1){
return i+1;
}
}
return len+1;
}
private void swap(int [] nums,int m,int n){
int tmp=nums[m];
nums[m]=nums[n];
nums[n]=tmp;
}
}
