02-1数组练习题

.经典题目

1.求二数之和:https://leetcode-cn.com/problems/two-sum/

思路：
使用hashMap，将遍历过的值放入其中，进行比较；
时间复杂度 n
空间负责度 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};
    } 
}

求三数之和：https://leetcode-cn.com/problems/3sum/

1.特殊情况：对于数组长度n,如果数组为null或者长度小于3，返回[]
2.对数组进行排序；
3.遍历排序后数组：
a.若num[i]>0,后面不可能再有等于0的情况，直接返回
b.对于重复元素，跳过，避免出现重复解；
c.左指针L=i+1，右指针R=n-1,当L<R 时，执行循环
当num[i]+num[L]+num[R]==0,执行循环，判断左边界和右边界是否和下一位重复，去除重复；
若和大于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.求众数:https://leetcode-cn.com/problems/majority-element/

摩尔投票法思路
候选人(cand_num)初始化为num[0]，票数count初始化为1
当遇到与cand_num相同的数，则票数count++，否则票数count--
当票数count为0时，更好候选人，并将票数count重置为1
遍历完数组后，cand_num即为最终答案
原理：
投票法是遇到相同的则票数+1,遇到不同的则票数-1
且多数元素的个数>n/2
其余元素的个数总和<=n/2
因此多数元素的个数-其余元素的个数总和>=1
时间复杂度n
空间复杂度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.求缺失的第一个正数：https://leetcode-cn.com/problems/first-missing-positive/

有一个前提：n个数组成的数组，那么最小正整数的范围一定在[1,n+1]之间
由于题目要求我们”只能使用常数级别的空间“，因此我们可以把原始的数组当做哈希表来使用。abstract
要找的数在[1,n+1],n+1不用找，前面元素找不到的时候，我们才返回n+1
思路:把1放在下标为0的地方，2放在坐标为1的地方

时间复杂度 n (while不会每次都循环，之多循环n次)
空间复杂度 1

public class Solution {

    public int firstMissingPositive(int[] nums) {
       int len=nums.length;
       for(int i=0;i<len;i++){
           //重点nums[nums[i]-1]!=nums[i],为啥不是num[i]!=i+1,这样对重复的数字会造成死循环
           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;
}
}