[Java][TwoPoints][LeetCode] Sum of Square Numbers #633

Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Example 1:

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

I suppose first this question is extension of Two Sum. Then I used HashSet to solve this question. But… The RunTime is too bad. So, I change my thinking to Two Points. small point is start from 0 and shift to right, large point is start from squrt(c) and shift to left. If sum of square of small point and square of large point lesser equal c, return true. If lesser than c, small point shift to right. If larger than c, large point shift to left.

一開始的思考方向是Two Sum的延伸，於是先做了一個HashSet的方式，但RunTime實在太差，練習使用TwoPoints。小指針從0開始往右移動，大指針從c開平方的整數值開始往左移動，如果小指針的平方與大指針的平方和為c，則為true。如果大於c則表示大指針過大，需要往左邊移動。反之，則小指針往右移動。