It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.
Apparently, many engineers take measures on the site called LetCode.
It is a site that trains the algorithmic power that can withstand the coding test that is done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.
I wrote it in a big way, but I have no plans to have such an interview at the moment.
However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.
I'm solving it with Python3.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day 64 "287. Find the Duplicate Number" starting from zero
Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.
Twitter I'm doing it.
** Technical Blog Started! !! ** ** I think the technology will write about LetCode, Django, Nuxt, and so on. ** This is faster to update **, so please bookmark it!
560. Subarray Sum Equals K The difficulty level is Medium. Excerpt from Top 100 Liked Questions.
Given an array of integers and an integer k, the problem is to find the total number of contiguous arrays whose sum is equal to k.
Example 1: Input:nums = [1,1,1], k = 2 Output: 2
Constraints:
The length of the array is in range [1, 20,000]. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
import collections
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
dic = defaultdict(int)
dic[0] = 1
count = calc = 0
for n in nums:
calc += n
dic[calc],count = dic[calc] + 1,count + dic[calc-k],
return count
# Runtime: 144 ms, faster than 44.41% of Python3 online submissions for Subarray Sum Equals K.
# Memory Usage: 17.9 MB, less than 10.96% of Python3 online submissions for Subarray Sum Equals K.
I wrote it using defaultdict.
I wasn't so conscious of the constraints, and thought about how to solve them for the time being.
The cumulative sum is stored in calc, the value is stored in the key part using a dictionary, the number of times the same value appears consecutively in the value part is saved, and the number of times the sum is encountered is also subtracted. By holding with -k] , the value according to the request is added to count`.
I got a hint from Solution and wrote it, but it looks great.
By the way, I haven't taken a lecture on specialized algorithms, but when I think about it, I don't really know how other people write algorithms.
My way of thinking
Vaguely think about how to write without thinking about programming once
↓
If you can get a good idea, write it on a piece of paper and think about whether the flow is correct.
↓
Find out and write good libraries and built-in functions to achieve that flow in Python
↓
Complete
It is a flow. If it doesn't work, I review the flow and rework it or write a new pattern roughly, and I wonder if my problem is to think about the flow. (Of course, I still haven't learned much about typical algorithms and data structures.) When I was a high school student, I didn't really work on mathematics for entrance exams, and when asked about integers, probabilities, and the number of cases, I often get confused.
I'm trying to solve math problems in order to overcome the problems, but I still have something I want to do, and the math I learn in the process is fun to do. When I was a student, I didn't want to do anything in mathematics, so I am working on it with a fresh feeling.
So far this time, thank you for your hard work.
Recommended Posts