Leetcode每天兩題3-第167題和第170題

03-06

話說找美女照片真的好難啊！要不長得一個樣，要不就是網紅臉+街臉。沒有美女照片寫不了代碼啊 (*?ω?)

天氣不錯，可惜我是個死宅。。。除了覓食估計我都不需要出門！馬上就要放假了，放假之前爭取不斷更。

167. Two Sum II - Input array is sorted

給定的有序數組和一個整數，從數組裡找出兩個數，這兩個數的和等於給定的整數，返回數組的下標（下標不從0開始）。原味↓

Given an array of integers that is already sorted in ascending order, 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 and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

代碼+注釋

class Solution {public: vector<int> twoSum(vector<int>& numbers, int target) { if (numbers.size() <= 0) return{}; //從開始位置和結束位置開始，每次從兩邊各取一個數，然後相加 //判斷和是否與目標值相等 //給定的是有序數組 int left = 0, right = numbers.size() - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) { return{ left + 1,right + 1 }; } else if (sum < target) left++; else right--; } return{}; }};

170.Two Sum III - Data structure design

設計一個TwoSum的數據結構，包含插入和查找（兩個元素的和與某個給定數相等）。

Design and implement a TwoSum class. It should support the following operations:add and find.

add - Add the number to an internal data structure.

find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

add(1); add(3); add(5);

find(4) -> true

find(7) -> false

代碼+注釋

class Solution {public: //添加元素 void add(int val) { m[val]++; } //找出是否存在兩個元素的和與給定值相等 //兩種情況：10=5+5；兩個相等的元素 //或者8=5+3；兩個不相等的元素 bool find(int val) { for(auto a:m) { int toFind = val - a.first; if ((toFind!=a.first&&m.count(toFind))|| (toFind == a.first && a.second > 1)) { return true; } } return false; } private : unordered_map<int, int> m;};