public class Solution {
public int[] TwoSum(int[] nums, int target) {
int max = nums.Length; //陣列的長度
for(int i = 0;i<max;i++) //從第一個元素開始找
{
int diff = target - nums[i]; //這一次遞迴跟target的差異值,後面就不用一直計算了
for(int j = i+1;j<max;j++) //j = i+1 (因為不能用同個元素,故從下一個開始)
{
if(nums[j] == diff) //當nums[j] = 剛剛得出的差異值時,回傳答案
{
return new int[2]{i,j};
}
}
}
return new int[2]{0,0}; //其實不會跑到的地方,因所有路徑都須回傳值而加上
}
}
時間複雜度 : O(n2)
方案2 – 使用內建的Array.FindIndex
public class Solution {
public int[] TwoSum(int[] nums, int target) {
int max = nums.Length; //陣列的長度
int index;
for(int i = 0;i<max;i++)
{
//跟target的差異值
int diff = target - nums[i];
index = Array.FindIndex(nums,i+1,x=>x == diff);
//如果有找到差異值 (Array.FindIndex回傳非-1)
if(index != -1)
{
return new int[2]{i,index};
}
}
return new int[2]{0,0};
}
}
public class Solution {
public int[] TwoSum(int[] nums, int target) {
Dictionary<int, int> dict = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++)
{
int diff = target - nums[i];
if (dict.ContainsKey(diff))
{
return new int[] {dict[diff], i};
}
if (!dict.ContainsKey(nums[i]))
{
dict.Add(nums[i], i);
}
}
return new int[]{0,0};
}
}
⭐時間複雜度 : O(n) ➡ C# Dictionary ContainsKey ≈O(1)
Dictionary 中的Key存的是 int值,Value則是存其index
直接用字典的ContainsKey 來判斷差異值是否存在,若有就取得其index並回傳
Java解決方案
方案1
class Solution {
public int[] twoSum(int[] nums, int target) {
int max = nums.length;
for(int i = 0;i<max;i++)
{
int diff = target - nums[i];
for(int j=i+1;j<max;j++)
{
if(nums[j] == diff)
{
return new int[]{i,j};
}
}
}
return new int[]{0,0};
}
}
❌概念上沒問題,但運行時間會過久而導致 Time Limit Exceeded 的錯誤 (所有的測試案例都可以通過)
class Solution {
public int[] twoSum(int[] nums, int target) {
int max = nums.length;
int index;
List<Integer> myList = new ArrayList<>();
for(int i = 0;i<max-1;i++)
{
int diff = target - nums[i];
myList = IntStream.of(nums).boxed().collect(Collectors.toList());
myList = myList.subList(i+1,max);
index = myList.indexOf(diff);
if(index != -1)
{
return new int[]{i,index+i+1};
}
}
return new int[]{0,0};
}
}
⭐方案3(推薦) – 使用 HashMap來儲存
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer>map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++)
{
int diff = target - nums[i];
if (map.containsKey(diff))
{
return new int[] {map.get(diff), i};
}
else
{
map.put(nums[i], i);
}
}
return new int[]{0,0};
}
}
⭐運行時間 – 3ms
Python3 解決方案
❌方案1 (不太推薦) ➡ 高機率會跑到逾時,運氣好會成功(?
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
left = nums[i+1:]
for j in range(len(left)):
if (nums[i] + left[j]) == target:
return i, j+i+1
⭐方案2 – hash table
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash_table={}
for i in range(len(nums)): #First, create the hash table
hash_table[nums[i]]=i
for i in range(len(nums)):
if target-nums[i] in hash_table:
if hash_table[target-nums[i]] != i:
return [i, hash_table[target-nums[i]]]
return [0,0]
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
var map = {};
for(var i = 0 ; i < nums.length ; i++){
var n = nums[i];
if(map[target-n] >= 0){
return [map[target-n],i]
}
else {
map[n] = i; //use map to store the value and index position
}
}
};
ai_front = {"insertion_before":"BEFORE","insertion_after":"AFTER","insertion_prepend":"PREPEND CONTENT","insertion_append":"APPEND CONTENT","insertion_replace_content":"REPLACE CONTENT","insertion_replace_element":"REPLACE ELEMENT","visible":"VISIBLE","hidden":"HIDDEN","fallback":"FALLBACK","automatically_placed":"Automatically placed by AdSense Auto ads code","cancel":"Cancel","use":"Use","add":"Add","parent":"Parent","cancel_element_selection":"Cancel element selection","select_parent_element":"Select parent element","css_selector":"CSS selector","use_current_selector":"Use current selector","element":"ELEMENT","path":"PATH","selector":"SELECTOR"};