数组、哈希_牛客博客

两数之和

给出一个整数数组，请在数组中找出两个加起来等于目标值的数，
你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的
假设给出的数组中只存在唯一解
例如：
给出的数组为 {20, 70, 110, 150},目标值为90
输出 index1=1, index2=2

菜鸡题解
最暴力的思路：类似于冒泡排序，将所有可能的两个数相加的组合列出来挨个比较。

import java.util.*;
public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        int[] rt=new int[2];
        for(int i=0;i<numbers.length;i++){
            for(int j=i+1;j<numbers.length;j++){
                if(target==(numbers[i]+numbers[j])){
                    rt[0]=i+1;
                    rt[1]=j+1;
                    return rt;
                }
            }
        }
        return rt;
    }
}

大神思路
原思路：

首先想到能不能排序。若是有序数组，将会节省不小的时间开销（target/2往后的不用看；每轮一旦两数和大于 target 即可 break）。
再看题目要求输出 index，若先排序 index 就乱了，貌似没戏。
还不死心，想能不能通过 Map 来存取改动前的 index。
取一种折中的办法，数组不用完全有序，只要设立一个 target/2 基准点即可（类似快排），因为两数不可能同时出现在 target/2 的同一侧！（貌似能成）
map存取所有移动过元素的原索引，以及所有左侧元素索引，这样只需遍历右侧的元素，看target与元素之差存在 map 中的值（索引）即可。
照着这个思路写完了，部分用例未通过（如[0,2,3,0],0，也就是 target 恰好等于最小值的情况）
抓耳挠腮过程中偷瞄了一眼 LeetCode 上的题解，泪流满面。相比之下我这都什么废物思路。直接给跪了，怒删代码。

LeetCode 题解思路：遍历，每次判断 target - current 是否在 Map 中，若在直接返回；若不在将 current 和对应索引存入 Map。
注意：因为每次找的是 target 和当前元素的差值，因此理论上不存在元素覆盖的问题（因为题目声明只有唯一解）。

public int[] twoSum (int[] numbers, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int cur = 0, tmp; cur < numbers.length; cur++){
        tmp = numbers[cur];
        if (map.containsKey(target - tmp)){
            return new int[] {map.get(target - tmp) + 1, cur + 1};
        }
        map.put(tmp, cur);
    }
    throw new RuntimeException("results not exits");
}

提示：可以通过return new int[] {1,2}返回一个数组对象且为[1,2]
注意：map中键为数组中的元素，值为数组下标。还有一点是先判断差值是否在map中，若不在，再进行put的操作。

有序数组去重

题目：26 easy

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int p=0,q=1;
        while(q<nums.length){
            if(nums[p]==nums[q]) q++;
            else{
                p++;
                nums[p]=nums[q];
            }
        }
        return p+1;
    }
}

双指针法

设置p、q指针
p始终指向有效数组的最后一位，q指向当前遍历的元素。q不断后移，但只有当a[p]!=a[q]时p才往后移。
当不重复时，将不重复元素添加到有效数组中去。并保持p指向有效数组最末。

通用解法

本题可转换为对于一个有序数组，每个数字最多只能有k个（k=1）。
我们进行如下考虑：

前k个数字可直接保留。
对于后面的数字，能保留的前提是：与当前写入位置前面的k个元素进行比较,若不相同则可保留.(即与当前写入位置idx-k比较，不同即可。)

举个🌰，我们令 k=1，假设有样例：[3,3,3,3,4,4,4,5,5,5]

设定变量 idx，指向待插入位置。idx 初始值为 0，目标数组为 []
首先我们先让第 1 位直接保留（性质 1）。idx 变为 1，目标数组为 [3]
继续往后遍历，能够保留的前提是与 idx 的前面 1 位元素不同（性质 2），因此我们会跳过剩余的 3，将第一个 4 追加进去。idx 变为 2，目标数组为 [3,4]
继续这个过程，跳过剩余的 4，将第一个 5 追加进去。idx 变为 3，目标数组为 [3,4,5]
当整个数组被扫描完，最终我们得到了目标数组 [3,4,5] 和答案 idx 为 3。

class Solution {
    public int removeDuplicates(int[] nums) {   
        return process(nums, 1);
    }
    int process(int[] nums, int k) {
        int idx = 0; //指向当前要写入的位置
        for (int x : nums) {//满足if的全部写入
            if (idx < k || nums[idx - k] != x) nums[idx++] = x;
        }
        return idx;
    }
}

作者：AC_OIer
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shua-chuan-lc-jian-ji-shuang-zhi-zhen-ji-2eg8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结

通用解法」是一种针对「数据有序，相同元素最多保留 k 位」问题更加本质的解法，该解法是从性质出发提炼的，利用了「数组有序 & 保留逻辑」两大主要性质。建议重点掌握 ~

移除某一元素

题目：27 easy

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

双指针法

可将数组分为前后两段：

前半段是有效部分，存储值不为val的元素

后半段是无效部分，存储值为val的元素

//作者：AC_OIer
class Solution {
  public int removeElement(int[] nums, int val) {
      int j = nums.length - 1;
      for (int i = 0; i <= j; i++) {
          if (nums[i] == val) {
              swap(nums, i--, j--);
          }
      }
      return j + 1;
  }
  void swap(int[] nums, int i, int j) {
      int tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
  }
}
//作者：我自己
class Solution {
  public int removeElement(int[] nums, int val) {
      int p=0,q=0;
      int count=0;
      while(q<nums.length){
          if(nums[q]!=val){
              nums[p]=nums[q];//p指向待写入位置，q指向当前位置
              p++;q++;//不必删除则后移
          }
          else{//需要被删除
              q++;
              if(q<nums.length && nums[q]!=val){
                 nums[p] = nums[q];
              }
              count++;//每次删除一个元素计数
          }
      }
      return nums.length-count;
  }
}

通用解法

同26题
设定变量idx指向待插入位置。初始值为0。
然后从题目的「要求/保留逻辑」出发，来决定当遍历到任意元素 x 时，应该做何种决策:

若x==val，则跳过该元素
若x!=val，则将x插入idx的位置，并让idx自增。

最终idx即为答案。

class Solution {
    public int removeElement(int[] nums, int val) {
        int idx = 0;
        for (int x : nums) {
            if (x != val) nums[idx++] = x;
        }
        return idx;
    }
}
//作者：AC_OIer
//我自己的解法的思路更符合通用解法

总结

对于诸如「相同元素最多保留 k 位元素」或者「移除特定元素」的问题，更好的做法是从题目本身性质出发，利用题目给定的要求提炼出具体的「保留逻辑」，将「保留逻辑」应用到我们的遍历到的每一个位置