iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 2
0

題目:

https://leetcode.com/problems/two-sum/
給一個陣列,返回兩個數字的索引,使它們相加到特定目標。

解題思路:

使用2個for迴圈查詢整個陣列相加是否符合目標值,符合時將其索引值放入陣列。

C版本:

int* twoSum(int* nums, int numsSize, int target) {
     static int answer[2] = {};
    
     for (int i = 0 ; i < numsSize; i++)
     {
        for (int j = i+1 ; j < numsSize ; j++)
        {
            if((nums [i] + nums [j]) == target)
            {
                answer[0] = i;
                answer[1] = j;
                    
                return answer;
            }
        }
     }
     return 0;
}

Javascript版本:

var twoSum = function(nums, target) {
    var result = [];
    for(var i = 0; i<nums.length; i++)
    {
        for(var j = i+1; j<nums.length; j++)
        {
            if((nums[i] + nums[j]) == target)
            {
                result.push(i);
                result.push(j);
                return result;
            }
        }
    }
};

時間複雜度為: O(nxn)

空間複雜度為: O(1)

優化版本解題思路:

建立一個哈希表,在一個for迴圈中利用差值所得到另一個數值,查詢訪哈希表內是否有存在,如果有的話則返回其索引值。

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    int[] result = new int[2];

    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(numbers[i])) {
            int index = map.get(numbers[i]);
            result[0] = index+1 ;
            result[1] = i+1;
            break;
        } else {
            map.put(target - numbers[i], i);
        }
    }

    return result;
    }
}

時間複雜度為: O(n)

空間複雜度為: O(1)

心得:

今天在看別人寫的文章時,發現有人跟我寫相同的主題,覺得我講的不清楚或不瞭解的話也可以到他那邊看看。
https://ithelp.ithome.com.tw/articles/10213193

程式Github分享:

https://github.com/SIAOYUCHEN/leetcode

本日分享:

Every present that you regret now is a result of a past you failed to give your best.
每一個令你後悔的現在,都有一個不夠努力地曾經


上一篇
DAY1 自我挑戰的開始(前言、問題與討論)
下一篇
DAY3 Reverse Integer
系列文
刷題記錄與人生分享34
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言