청정알고리즘

문제

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

풀이

list를 순회하면서 실제 덧셈을 하는 것 같이 계산을 해준다.

받아올림할 변수인 carry를 잘 관리하는 것이 핵심.

Time Complexity : $O(n)$

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry=0;
        ListNode *ans=new ListNode(0);
        ListNode *p=l1;
        ListNode *q=l2;
        ListNode *now=ans;
        while(p!=NULL || q!=NULL)
        {
            int s =(p?p->val:0)+(q?q->val:0)+carry;
            carry = s/10;
            now->next = new ListNode(s%10);
            now = now->next;
            if(p) p=p->next;
            if(q) q=q->next;
        }
        if(carry) now->next = new ListNode(carry);
        return ans->next;
    }  
};

문제

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.

풀이

해쉬맵을 이용해서 nums에 있는 모든 숫자들을 (숫자, index) pair로 저장한다.

그 후 nums를 모두 돌면서, 합이 target이 되는 원소가 nums에 존재하는 지를 찾으면 끝난다.

주의할점은 index를 확인하면서 현재 index와 더할 숫자의 index가 다른것을 체크해 주어야한다.

Time Complexity : $O(n)$

코드

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_map<int,int> m;
        vector ret;
        for(int i=0;i<nums.size();i++) m[nums[i]]=i;
        
        for(int i=0;i<nums.size();i++)
        {
            int t = target-nums[i];
            if(m.find(t)!=m.end() && m[t]!=i)
            {
                ret.push_back(i);
                ret.push_back(m[t]);
                return ret;
            }
        }
        return nums;
    }
};