current position:Home>leetcode 1995. Count Special Quadruplets(python)
leetcode 1995. Count Special Quadruplets(python)
2022-01-31 13:33:26 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 13 God , Check out the activity details :2021 One last more challenge 」
describe
Given a 0-indexed integer array nums, return the number of distinct quadruplets (a, b, c, d) such that:
- nums[a] + nums[b] + nums[c] == nums[d], and
- a < b < c < d
Example 1:
Input: nums = [1,2,3,6]
Output: 1
Explanation: The only quadruplet that satisfies the requirement is (0, 1, 2, 3) because 1 + 2 + 3 == 6.
Copy code
Example 2:
Input: nums = [3,3,6,4,5]
Output: 0
Explanation: There are no such quadruplets in [3,3,6,4,5].
Copy code
Example 3:
Input: nums = [1,1,1,3,5]
Output: 4
Explanation: The 4 quadruplets that satisfy the requirement are:
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5
Copy code
Note:
4 <= nums.length <= 50
1 <= nums[i] <= 100
Copy code
analysis
According to the meaning , Give an example from 0 Start indexing the list nums , The title requires us to return different quads ( a , b , c , d ) The number of , bring :
- nums[a] + nums[b] + nums[c] == nums[d]
- a < b < c < d
The most direct way is to use violent solutions , Ideas as follows :
- Initialize counter result by 0
- Use built-in functions combinations(nums, 4) Find all the quaternion combinations , Then traverse all combinations to determine whether they meet cb[0] + cb[1] + cb[2] == cb[3] , If yes, the counter result Add one
- Return after traversal result
answer
class Solution(object):
def countQuadruplets(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for cb in combinations(nums, 4):
if cb[0] + cb[1] + cb[2] == cb[3]:
result += 1
return result
Copy code
Running results
Runtime: 1780 ms, faster than 9.01% of Python online submissions for Count Special Quadruplets.
Memory Usage: 13.3 MB, less than 74.59% of Python online submissions for Count Special Quadruplets.
Copy code
analysis
In addition, four layers of circulation can be used , Look for the combination of all four indexes to find the quaternion combination that meets the meaning of the question , This is also a violent solution , It's just written differently , The result of running is similar to the above .
answer
class Solution(object):
def countQuadruplets(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for i in range(len(nums)-3):
for j in range(i+1, len(nums)-2):
for k in range(j+1, len(nums)-1):
for l in range(k+1, len(nums)):
if nums[i]+nums[j]+nums[k] == nums[l]:
result += 1
return result
Copy code
Running results
Runtime: 1588 ms, faster than 37.70% of Python online submissions for Count Special Quadruplets.
Memory Usage: 13.4 MB, less than 74.59% of Python online submissions for Count Special Quadruplets.
Copy code
analysis
After reading the forum, the great God used the dictionary solution, which is very clever , Mainly used nums[a] + nums[b] == nums[d] - nums[c] This equation , take nums[a] + nums[b] Save in dictionary , Just traverse c and d The index of , The time complexity can be reduced to O(n^2) , The performance improvement is too great !!
answer
class Solution(object):
def countQuadruplets(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
res = 0
d = defaultdict(int)
d[nums[0] + nums[1]] = 1
for i in range(2, n - 1):
for j in range(i + 1, n):
res += d[nums[j] - nums[i]]
for j in range(i):
d[nums[i] + nums[j]] += 1
return res
Copy code
Running results
Runtime: 48 ms, faster than 99.18% of Python online submissions for Count Special Quadruplets.
Memory Usage: 13.3 MB, less than 93.44% of Python online submissions for Count Special Quadruplets.
Copy code
Original link :leetcode.com/problems/co…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201311333250147.html
The sidebar is recommended
- [algorithm learning] 1108 IP address invalidation (Java / C / C + + / Python / go / trust)
- Test platform series (71) Python timed task scheme
- Java AES / ECB / pkcs5padding encryption conversion Python 3
- Loguru: the ultimate Python log solution
- Blurring and anonymizing faces using OpenCV and python
- How fast Python sync and async execute
- Python interface automation test framework (basic) -- common data types list & set ()
- Python crawler actual combat, requests module, python realizes capturing video barrage comments of station B
- Python: several implementation methods of multi process
- Sword finger offer II 054 Sum of all values greater than or equal to nodes | 538 | 1038 (Java / C / C + + / Python / go / trust)
guess what you like
-
How IOS developers learn python programming 3-operator 2
-
How IOS developers learn python programming 2-operator 1
-
[Python applet] 8 lines of code to realize file de duplication
-
Python uses the pynvml tool to obtain the working status of GPU
-
Data mining: Python actual combat multi factor analysis
-
Manually compile opencv on MacOS and Linux and add it to Python / C + + / Java as a dependency
-
Use Python VTK to batch read 2D slices and display 3D models
-
Complete image cutting using Python version VTK
-
Python interface automation test framework (basic) -- common data types Dict
-
Django (make an epidemic data report)
Random recommended
- Python specific text extraction in actual combat challenges the first step of efficient office
- Daily python, Part 8 - if statement
- Django model class 1
- The same Python code draws many different cherry trees. Which one do you like?
- Python code reading (Chapter 54): Fibonacci sequence
- Django model class 2
- Python crawler Basics
- Mapping 3D model surface distances using Python VTK
- How to implement encrypted message signature and verification in Python -- HMAC
- leetcode 1945. Sum of Digits of String After Convert(python)
- leetcode 2062. Count Vowel Substrings of a String(python)
- Analysis of Matplotlib module of Python visualization
- Django permission management
- Python integrated programming -- visual hot search list and new epidemic situation map
- [Python data collection] scripy realizes picture download
- Python interface automation test framework (basic part) -- loop statement of process control for & while
- Daily python, Chapter 9, while loop
- Van * Python | save the crawled data with docx and PDF
- Five life saving Python tips
- Django frequency control
- Python - convert Matplotlib image to numpy Array or PIL Image
- Python and Java crawl personal blog information and export it to excel
- Using class decorators in Python
- Untested Python code is not far from crashing
- Python efficient derivation (8)
- Python requests Library
- leetcode 2047. Number of Valid Words in a Sentence(python)
- leetcode 2027. Minimum Moves to Convert String(python)
- How IOS developers learn Python Programming 5 - data types 2
- leetcode 1971. Find if Path Exists in Graph(python)
- leetcode 1984. Minimum Difference Between Highest and Lowest of K Scores(python)
- Python interface automation test framework (basic) -- basic syntax
- Detailed explanation of Python derivation
- Python reptile lesson 2-9 Chinese monster database. It is found that there is a classification of color (he) desire (Xie) monsters during operation
- A brief note on the method of creating Python virtual environment in Intranet Environment
- [worth collecting] for Python beginners, sort out the common errors of beginners + Python Mini applet! (code attached)
- [Python souvenir book] two people in one room have three meals and four seasons: 'how many years is it only XX years away from a hundred years of good marriage' ~?? Just come in and have a look.
- The unknown side of Python functions
- Python based interface automation test project, complete actual project, with source code sharing
- A python artifact handles automatic chart color matching