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

  • 

大家明天见