双指针 [m] #633 Sum of Square Numbers

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

总结

  1. 第二个指针(Max边界值)设置为sqrt (target):
int i = 0, j = (int) Math.sqrt(c);

因为最多只需要遍历一次 0~sqrt(target),所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量,因此空间复杂度为 O(1)。

  1. 本题中两个指针可以重合,即指向同一个值。
  2. 指针移动的规则同#167 题一样
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容