数组的面试题(面试关于数组的算法题)

导语：面试题库-数组类n-Sum之2-Sum

n-sum问题，是面试常考的问题。其中最简单的two-sum问题，也是leetcode(力扣)的第一道题。

简单说就是给一个数组和一个目标数t，找出n个元素和为t。

首先说最简单的two-sum。

先把方法定义出来:

两个元素的下标用数组返回, int[] twoSum(int[] a, int target)

第一想法：

两层for循环，if(a[i] + a[j]) == t, 返回下标。时间复杂度O(n^2), 显然这题不是让你写这样的算法。

第二想法：

看看能否一趟算法搞定。

一趟算法中，在下标i往前行进(i++)的过程中，我们能拿到a[i]，我们要找的另一个值是t-a[i].

加速查找问题的方法最简单的就有两个：1 二分搜索(O(logn)); 2用HashMap(O(1))，

所以在不考虑空间复杂度的情况下，使用HashMap: 显然查找所用的key是具体的值，要找的value是下标，所以每拿到一个a[i]，put(a[i], i) get(t-a[i]) 能get到就搞定了。

调整下顺序得到下列代码：

int[] twoSum(int[] a, int t) {  Map<Integer, Integer> map = new HashMap<>();  int[] res = new int[2];  for (int i = 0; i < a.length; i++) {    if(map.get(t-a[i]) != null) {      int[0] = map.get(t-a[i]);      int[1] = i;    } else {      map.put(a[i], i);    }    return res;  }        

本文内容由小梓整理编辑！