2021-01-19 https://leetcode.com/problems/sum-of-square-numbers/
题目描述:
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
Example 2:
Input: c = 3
Output: false
总结
- 第二个指针(Max边界值)设置为sqrt (target):
int i = 0, j = (int) Math.sqrt(c);
因为最多只需要遍历一次 0~sqrt(target),所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量,因此空间复杂度为 O(1)。
- 本题中两个指针可以重合,即指向同一个值。
- 指针移动的规则同#167 题一样