問題描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

問題分析

人話：給出一個數(shù)字數(shù)組，找出數(shù)組內(nèi)兩個相加等于目標數(shù)字的元素，這兩個元素的下標組成的數(shù)組就是問題的答案了
一開始我想到的最簡單的方法是雙重循環(huán)，比如：【1，2，3】，當?shù)谝粚友h(huán)的當前元素是1的時候，就對【2，3】進行循環(huán)，分別判斷1+2和1+3是否等于目標數(shù)字，如果都不符合就繼續(xù)第一層循環(huán)。因為我使用的語言是JavaScript，JavaScript有個方法indexOf，可以定位元素在數(shù)組的位置，所以可以對第二層循環(huán)進行封裝。

問題解決

 var twoSum = function(nums, target) {
 let result=[];   //最終結(jié)果
 //len = nums.length：把nums的長度緩存起來，可以節(jié)省循環(huán)中每一次查詢nums長度的時間
 for(let i = 0,len = nums.length; i < len; i++){
     for(let j = i+1, len = nums.length; j<len; j++){
        if(nums[i]+nums[j]==target){
             result.push(i);
             result.push(j);
             break;
         }
     }
     if(result.length){
         break;
     }
 }
 return result;
 };

使用indexOf方法：

var twoSum = function(nums, target) {
 let result=[];
 for(let i = 0, len = nums.length; i < len; i++){
     let index = nums.indexOf( target - nums[i] );
     if(index >= 0 && index != i){
         result.push(i);
         result.push(index);
         break;
     }
 }
 return result;
 };
//index != i：因為indexOf是返回數(shù)組中第一個符合條件的元素的下標，比如[ 1, 2, 1].indexOf( 1 )，結(jié)果是0。index != i目的是過濾掉下標與當前循環(huán)下標相同的元素。

第一種方法的時間復雜度是O(n * (n -1))，即O(n * n)，LeetCode顯示的代碼運行時間是124ms；第二種方法的時間復雜度是O( n * n)，運行時間為220ms。兩者的時間復雜度相同，但是細微的差別就是第二種方法在nums為【3，3】的情況下需要運行完兩個循環(huán)(indexOf實質(zhì)上就是一層循環(huán))，而第一種方法在兩層循環(huán)中各循環(huán)一次就能找到最終結(jié)果。

總結(jié)

1.學會計算算法的時間復雜度，以此來比較算法在當前情況的優(yōu)劣，盡量使用時間復雜度低的算法
2.舉一反三，面對一個問題時，應該想辦法去思考多種解決方法，擴展思路，在多個解決方法中選擇最優(yōu)。
3.閱讀英文文檔或文章時，文檔中的代碼會幫助我們理解文檔，就算讀不懂文檔，看代碼也能解決問題。