読者です 読者をやめる 読者になる 読者になる

3Sum Closest : LeetCode

LeetCode 3Sum いもす法

Problem

leetcode.com

与えられたInt型の配列numsの要素の内、3つ選んだ要素の和がtargetに最も近い値を見つける問題。

Solution

全列挙によるO(N3)の解法

配列の全ての3つの要素の和を算出し、その中から一番targetに近い値を見つける事で問題を解くことができる。 この時、配列の要素数をNとすると計算量はO(N3)となる。

いもす法によるO(N2)の解法

探索を始める前に配列をソートすることで計算量を小さくすることができる。 選択する3つの要素のインデックスをそれぞれleft, mid, rightとすると、leftを固定し、3つの要素の和に対してtargetより大きければrightを−1し、小さければmidを+1する。これleftを0 ~ N - 2まですることで計算量O(N2)で解くことができる。

Source Code

Maximum Size Subarray Sum Equals k

LeetCode HashMap

Problem

discuss.leetcode.com

Solution

This problem can be solved by using HashMap effectively. First, we store each sum of range from 0 to i (0 <= i < N). While we traverse the array, we check if the (sum - k) is stored in HashMap. If the number is in the map, the size of subarray that its sum equals k is i - hash.get(sum - k). This is the most important point.

Source Code

Alien Dictionary : LeetCode

LeetCode Topological Sort Google

Problem

https://leetcode.com/problems/alien-dictionary/?tab=Description

Solution

This problem can be solved by using Topological Sort.

Cracking The Coding Interview Binary Tree LinkedList

Problem

leetcode.com

Solution

This problem can be solve by DFS with depth of tree. In my code, lists.size() == depth means that the traversing depth changes.

Source Code

Maximum Product of Word Lengths

Bit Manipulation Cracking The Coding Interview

Problem

leetcode.com

Solution

This problem can be solved effectively by using bit manipulation. We can manage the count of appearance of each letters. Lower case letters are transformed to Integer within 26. This takes 0(N2) time.

Source Code