Day 2 - Two Sum

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
廢話不多說開始今天的解題Day~

1. Two Sum

Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example

Example1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example2

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example3

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

解題

題目

首先先簡單的翻譯一下題目
給一個陣列與一個目標值，可以從陣列中找到兩個值相加等於目標值，要回傳的內容則是這兩個值在陣列中的位址。
這邊題目是假設剛好只會有一個解，且相同的元素不能用第二次，但看到Example3的測資，我想題目應該是指在陣列中每個位址的元素只能被使用一次。

Think

第一個想法就是暴力解 (ﾟ∀ﾟ)，有想到其他的再改~

作法大致上是這樣

• 這邊我是用減法的方式，用兩層for loop，第一層就是每一個元素，第二層則是抓第一層元素的下一個位址之後的所有元素。
• C程式碼還有些bug在處理中。

Code

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        remain = 0
        
        for num1 in range(len(nums)):
            remain = target - nums[num1]
            for num2 in range(num1+1, len(nums)):
                if remain == nums[num2]:
                    return [num1,num2]

C

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *indices = (int*)malloc(sizeof(int)*2);
    bzero(indices , sizeof(int)*2);

    int remain = 0;
    
    for (int num1=0 ; num1<numsSize-1 ; num1++){
        remain = target - nums[num1];
        indices[0] = num1;
        
        for (int num2=num1+1 ; num2<numsSize ; num2++){
            // printf("%d: %d, %d: %d :=: %d\n", num1, nums[num1], num2, nums[num2], remain);
            if (remain == nums[num2]){
                indices[1] = num2;
                remain = 0;
                break;
            }     
        }
        
        if (remain == 0)
            break;
    }
    
    *returnSize = 2;
    return indices;
}

Result

• Python

  • 

• C

  • 

大家明天見