問題描述
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
翻譯
思路
解法1：雙循環(huán)溺欧，簡單暴力
時(shí)間復(fù)雜度：O(n^2) 空間復(fù)雜度：O(1)
兩層循環(huán)旺矾，遍歷兩次數(shù)組，相加合為target的值的下標(biāo)就是所需求值
<pre>
'' /**
'' * 時(shí)間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(1)
'' * 解題思路：
'' * 嵌套兩個(gè)循環(huán)遍歷就是了，感覺好low啊，不過竟然可以通過
'' * @param nums
'' * 數(shù)組
'' * @param target
'' * 和值
'' * @return
'' * 數(shù)值對應(yīng)的下標(biāo)
'' */
'' public int[] twoSum(int[] nums, int target) {
'' int k = 0;
'' int y = 0;
'' for(int i = 0; i < nums.length; i++) {
'' for(int j = i + 1; j < nums.length; j++) {
'' if(nums[i] + nums[j] == target) {
'' k = i;
'' y = j;
'' break;
'' }
'' }
'' }
'' int[] a = {k + 1, y + 1};
'' return a;
'' }
</pre>
解法2：hashMap
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)
將數(shù)組轉(zhuǎn)化為hashMap岭接，key為數(shù)值富拗，value為數(shù)值對應(yīng)的下標(biāo)。
<pre>
'' /**
'' * 時(shí)間復(fù)雜度O(n)
'' * 解題思路：
'' * 將數(shù)組轉(zhuǎn)化為hashMap鸣戴，key為數(shù)值啃沪，value為數(shù)值下標(biāo)
'' * 遍歷數(shù)組：
'' * 若Map中不包含當(dāng)前數(shù)值，則將key:target - num;value=i添加到Map窄锅，target - value表示與之對應(yīng)的數(shù)值创千，i表示數(shù)組下標(biāo)
'' * 若Map中包含當(dāng)前數(shù)值，說明之前有一個(gè)數(shù)num1入偷，與當(dāng)前的數(shù)值num2是對應(yīng)的签餐，取出Map中num1記錄的下標(biāo)值及當(dāng)前的i就是所需的下標(biāo)值
'' * @param nums
'' * 數(shù)組
'' * @param target
'' * 和值
'' * @return
'' * 數(shù)值對應(yīng)的下標(biāo)
'' */
'' public int[] twoSum_type2(int[] nums, int target) {
'' int[] a = new int[2];
'' Map<Integer, Integer> numsMap = new HashMap<Integer, Integer>();
'' for(int i = 0; i < nums.length; i++) {
'' if(numsMap.containsKey(nums[i])) {
'' a[0] = numsMap.get(nums[i]) + 1;
'' a[1] = i + 1;
'' } else {
'' numsMap.put(target - nums[i], i);
'' }
'' }
'' return a;
'' }
</pre>
解法3：雙指針夾逼
時(shí)間復(fù)雜度：O(nlog^n) 空間復(fù)雜度：O(n)
排序的時(shí)間復(fù)雜度為O(logn)，雙指針夾逼的時(shí)間復(fù)雜度為O(n)盯串，先排序再用雙指針夾逼氯檐，因此時(shí)間復(fù)雜度為O(nlongn)
<pre>
'' /**
'' * 時(shí)間復(fù)雜度O(n*log^n)
'' * 解題思路：
'' *
'' * @param nums
'' * 數(shù)組
'' * @param target
'' * 和值
'' * @return
'' * 數(shù)值對應(yīng)的下標(biāo)
'' */
'' public int[] twoSum_type3(int[] nums, int target) {
'' int[] a = new int[2];
''
'' int head = 0;
'' int tail = nums.length - 1;
'' //記錄數(shù)值對應(yīng)的下標(biāo)
'' double[] numsCopy = new double[nums.length];
'' for(int i = 0; i < nums.length; i++) {
'' numsCopy[i] = nums[i] + 0.01 * i;
'' }
'' //排序
'' Arrays.sort(numsCopy);
'' //遍歷數(shù)組，雙指針夾逼
'' while (head < tail) {
'' if(Math.floor(numsCopy[head]) + Math.floor(numsCopy[tail]) < target) {
'' head++;
'' } else if(Math.floor(numsCopy[head]) + Math.floor(numsCopy[tail]) > target) {
'' tail--;
'' } else {
'' a[0] = (int)(Math.ceil((numsCopy[head] - Math.floor(numsCopy[head])) * 100)) + 1;
'' a[1] = (int)(Math.ceil((numsCopy[tail] - Math.floor(numsCopy[tail])) * 100)) + 1;
'' break;
'' }
'' }
''
'' return a;
'' }
</pre>
