民治做网站百度pc网页版

暴力解法：两个for循环，寻找和为target的两个数的索引

时间复杂度：O(n2)

空间复杂度：O(1)

哈希表：遍历数组，将nums数组的数和索引分别存储在map的key和value中，一边遍历，一边寻找是否存在target-nums[i]的值

时间复杂度：O(n)

空间复杂度：O(n)

为什么哈希表的方法可以不用遍历两遍？

因为map集合可以直接从key获取value值，也就是直接获取索引；但数组不能够直接获取，只能通过遍历的方式

import org.junit.Test;import java.util.HashMap;
import java.util.Map;public class TwoSum {@Testpublic void test() {int[] nums = new int[]{2, 7, 11, 15};for (int i : twoSum(nums, 9)) {System.out.print(i + " ");}}public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (hashtable.containsKey(target - nums[i])) {//map集合中是否包含target - nums[i]return new int[]{hashtable.get(target - nums[i]), i};//如果包含，返回target - nums[i]的value值/索引和i}hashtable.put(nums[i], i);//将nums数组的数和索引分别存储在map的key和value中}return null;}}