雙重循環、桶排序、HashMap

題目鏈接：兩數之和

1.雙重循環，最基本的方法，速度慢O(n^2)，但無需新空間。 public int[] twoSum(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {int temp = target - nums[i];for (int j = i + 1; j < nums.length; j++) {if (nums[j] == temp) {int[] res = {i, j};return res;}}}return null; }

2.桶排序法，速度快O(n)，但空間不確定性太大O(?)。

public int[] twoSum(int[] nums, int target) {int i = 0, len = nums.length;int max = nums[0];int min = nums[0];for (i = 1; i < len; i++) {if (nums[i] > max) max = nums[i];if (nums[i] < min) min = nums[i];}int temp = min;if (target - max < min) min = target - max;if (target - temp > max) max = target - temp;int[] mark = new int[max - min + 1 + 1];int offset = 0 - min;for (i = 0; i < len; i++) {mark[nums[i] + offset] = i + 1;}for (i = 0; i < len; i++) {int index = mark[target - nums[i] + offset] - 1;if (index != -1 && index != i) {int[] res = {i, index};return res;}}return null; }

3.hash法，利用hash表中查詢比線性查詢快的特點O(n)，且所需空間可以確定O(n)。
Java中HashMap底層實現即為HashMap，故此處使用HashMap。

public int[] twoSum(int[] nums, int target) {HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; i++) {map.put(nums[i], i);}for (int i = 0; i < nums.length; i++) {Integer temp = map.get(target - nums[i]);if (temp != null && temp != i) {int[] res = {i, temp};return res;}}return null; }

總結

以上是生活随笔為你收集整理的leetcode之Tow Sum两数之和的三种思路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。